If the blocks are different colors, this couldn’t be a simpler quiz. Then you reveal the blocks and ask the prover to identify Block A. You designate one block as “Block A” and the other as “Block B.” Then you place the blocks behind your back and randomly switch which hand holds which block. Let’s say the prover tells you that the two blocks are different colors. Moreover, you can’t verify someone else’s solution.īut you’re allowed to interrogate this person, whom we’ll call the prover. Someone places two blocks on the table in front of you and asks whether the blocks are the same or different colors. To understand the first leap, imagine that you’re colorblind.
Prior to Natarajan and Wright’s work, verification power had increased in two big leaps. In particular, computer scientists would like to know how this class changes as you give the verifier new ways to check the truth of a solution. Since then, NP has been the most intensively studied class of problems in computer science.
They called the class “NP,” for nondeterministic polynomial time. In the 1970s computer scientists defined a class of problems that are easy to verify, even if some are hard to solve. “It’s easy, given a proper three-coloring, to check that it works,” said John Wright, a physicist at the Massachusetts Institute of Technology who wrote the new paper along with Anand Natarajan of Caltech. As a result, a computer doesn’t take much longer to check a three-coloring of a graph with 60 vertices than it does to check a graph with 20 vertices.
As the graph gets bigger, the time it takes to do this increases slowly, in what’s called polynomial time. You’d just go through the vertices one by one, examining their connections. It wouldn’t take long to check whether their claim is true. If, say, finding a solution for a graph with 20 vertices takes 3 20nanoseconds - a few seconds total - a graph with 60 vertices would take on the order of 3 60 nanoseconds, or about 100 times the age of the universe.īut let’s say someone claims to have three-colored a graph. In general, the time it takes to find a three-coloring of a graph (or determine that none exists) increases exponentially as the size of the graph increases. This “three-color” problem is hard to solve. The person asks you if it’s possible to color the vertices of the graph using only three colors, such that no connected vertices have the same color.
When a problem is hard to solve but easy to verify, finding a solution takes a long time, but verifying that a given solution is correct does not.įor example, imagine someone hands you a graph - a collection of dots (vertices) connected by lines (edges). Even if the oracle promises to tell you answers to problems that are far beyond your own ability to solve, there’s still a way to ensure the oracle is telling the truth. The new work essentially gives us leverage over that powerful oracle. Quantum computers barely exist now but have the potential to revolutionize computing in the future. The research applies to quantum computers - computers that perform calculations according to the nonintuitive rules of quantum mechanics. “It seems insane,” said Thomas Vidick, a computer scientist at the California Institute of Technology who wasn’t involved in the new work. They describe a method that makes it possible to check answers to problems of almost incomprehensible complexity. In a paper released in April, two computer scientists dramatically increased the number of problems that fall into the hard-to-solve-but-easy-to-verify category. Turns out, the answer is: Almost unimaginably complicated. Given that, computer scientists want to know: How complicated can a problem be while still having a solution that can be verified? Some problems are too hard to solve in any reasonable amount of time. This is the crux of one of the central problems in computer science. You’d want some way to verify that what the oracle told you was true. While you might be intrigued, you’d have a hard time trusting it. Imagine someone came along and told you that they had an oracle, and that this oracle could reveal the deep secrets of the universe.