25
$\begingroup$

Assuming P $\neq$ NP, NP-complete problems are "hard to solve, but have answers that are easy to check." Does it make any sense to consider the opposite, that is, problems for which it's easy to compute a correct answer, but hard to verify an arbitrary purported solution?

I think such a problem would imply either:

  1. Exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.

  2. Some "correct" answers are easy to compute, but others are difficult to find.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ I doubt it. If an answer is easy to compute, the choice of certificate is easy: supply the purported answer with the problem, and "check" the answer by solving the problem, and seeing whether the purported answer is actually the answer. $\endgroup$ – Patrick87 Sep 19 '12 at 20:23
  • 1
    $\begingroup$ @Patrick87 - I think I addressed this in the question. What about a multi-valued function $f$ that associates a set of values $I_f(x) = \{y_1, y_2, \dots \}$ with an input $x$? Assume that $|I_f(x)| = 2^{|x|}$, and that it's easy to pick an element from $I_f(x)$, but given $z$ it's hard to determine whether $z \in I_f(x)$. $\endgroup$ – rphv Sep 19 '12 at 20:43
  • 2
    $\begingroup$ @Patrick87 The solver may be deterministic and output only one of all existing answers. You then need an efficient way to check whether two solutions are equivalent. Can equivalence on a set be harder than solving a problem on it? $\endgroup$ – Raphael♦ Sep 19 '12 at 21:18
  • $\begingroup$ I actually missed that part, sorry. Still, I'm inclined to doubt the premise. I'll think about it a bit more and come back if I have more pertinent thoughts. $\endgroup$ – Patrick87 Sep 19 '12 at 21:19
  • 1
    $\begingroup$ A certificate usually means that there is an easy way to reconstruct a proof, so by definition if you provide a certificate the verification is easy. A solution without a certificate might be hard. $\endgroup$ – Gilles 'SO- stop being evil' Sep 20 '12 at 0:43
24
$\begingroup$

If you are fine with artificial problems, you can make plenty of them. Here are a few:

  • Given a positive integer n in unary, answer a satisfiable 3CNF formula in n Boolean variables.
    Giving one satisfiable 3CNF formula is easy, but deciding whether a given 3CNF formula is satisfiable or not is 3SAT, a well-known NP-complete problem.
  • There is no input. Just answer a Turing machine which halts (when run with an empty input tape).
    Giving one such Turing machine is easy, but whether a given Turing machine halts or not is undecidable.

Added: By the way, I do not think that what you wrote in the last paragraph holds:

I think such a problem would imply exponentially many "correct" answers for any given input, because otherwise verification could be carried out by simply computing all of the correct answers.

If the problem has one solution, then indeed checking an answer is no harder than computing the correct solution. However, if the problem has one easy solution and one difficult solution, then you cannot compute all the solutions efficiently. Here is one such problem (which is very artificial):

  • Given a Turing machine M, answer one of the following statements that is true: “M halts on empty input tape,” “M does not halt on empty input tape,” and “M is a Turing machine.”
    Giving one solution is easy: you can always choose “M is a Turing machine.” However, whether a given answer is correct or not is undecidable. Note that in this problem, there are only two solutions for each instance.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there a reasonable way to define formally what it means for such problems to be “artificial”? (By “reasonable”, I mean something we can widely agree upon, like saying that a definition of “computable” captures our intuition of what it should mean.) $\endgroup$ – Gilles 'SO- stop being evil' Sep 19 '12 at 23:02
  • $\begingroup$ @Gilles: No, I do not think so. I called these problems “artificial” because it is very unlikely that someone encounters these problems first and then finds out that it is easy to make one answer and hard to decide the correctness of a given candidate of answer. But this “artificialness” is by no means a rigorous notion. $\endgroup$ – Tsuyoshi Ito Sep 19 '12 at 23:12
  • $\begingroup$ @Tsuyoshi Ito - Thank you for your clear answer. I've edited the last paragraph to reflect your insight. $\endgroup$ – rphv Sep 20 '12 at 19:09
2
$\begingroup$

Although Tsuyoshi Ito's answer covers the "main" answer, there were two subtler notes I wanted to add.

  1. Even when the solution is hard to verify, checking the solution is still easy to check with a short proof string. That is, by extending the solution a bit with extra information, it becomes easily checkable; the verification is always in NP. One way to see this is that the agent computing a solution can record all the random bits they use, and then the verifier can use that same random string to execute the same computation. (The prover must use random bits, otherwise they always output the same answer, and the verifier can always easily check by computing an answer by the same method.)

  2. For quantum computers, this is a very open question. For classical computers, the verifier can always do something like simulating the prover and checking that they get the same answer. It's entirely possible that for some tricky problem, there is quantum algorithm which produces a uniform distribution across all (exponentially many) solutions, which are hard to verify. You can't re-run the prover, because you will most likely get a different answer each time.

    As a example of a similar kind of issue, the Deutsch-Jozsa problem suffers from this a bit. If an oracle is not a balanced function, then a quantum computer can quickly determine that this is the case, but there is no short proof that would allow a classical computer to verify this. (This is only a "similar" issue because it can still be checked by another quantum computer, and the checking is also in classical BPP even if it's not in P.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.