21
$\begingroup$

So I understand the idea that the decision problem is defined as

Is there a path P such that the cost is lower than C?

and you can easily check this is true by verifying a path you receive.

However, what if there is no path that fits this criteria? How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Personally, I had only heard the class NP meant poly-time verification, but had never seen the restriction that that only means verifying answers of "yes, here is the solution". It seems intuitive to imagine that you have to be able to verify any solution in poly-time. $\endgroup$ – wjmccann Jan 25 '18 at 20:11
36
$\begingroup$

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances.

The class of problems where you can verify "no" instances in polynomial time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you describe, "Is there no TSP path with length at most $C$?" is also in co-NP: if you unpick the double-negation, a "no" instance to that problem is a "yes" instance to TSP and we can verify those in polynomial time.

There are some problems, such as integer factorization and any problem in P, that we know to be in both NP and co-NP. (Thanks to user21820 for pointing this out.)

It's not known whether NP and co-NP are the same set of problems. If they're the same, then we can verify both "yes" and "no" instances of TSP. If they're different, then P$\,\neq\,$NP, since we know that P$\,=\,$co-P (because we can just negate the answer of a deterministic machine, giving the answer to the complement problem).

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ It may be worth mentioning that we know some problems that are in both NP and coNP, but that we do not know whether they are in P or not, such as integer factorization. $\endgroup$ – user21820 Jan 19 '18 at 16:02
  • $\begingroup$ @user21820 Integer factorization is not a decision problem. Primality is a decision problem and for years it was known to be in both NP and co-NP. Eventually it was shown to be in P as well. I don't know if there are still problems known to be in both NP and co-NP without having been shown to be in P. $\endgroup$ – kasperd Jan 20 '18 at 16:04
  • 4
    $\begingroup$ @kasperd: It is a well-known fact that integer factorization when made into a decision problem (Does n have a prime factor less than m?) is in both NP and coNP (both yes/no instances can be verified in polynomial time via the AKS primality test given the prime factorization as certificate), but is not yet shown to be in P. $\endgroup$ – user21820 Jan 20 '18 at 16:16
  • 1
    $\begingroup$ @user21820 There are much simpler and faster ways to verify a factorization than AKS. $\endgroup$ – kasperd Jan 20 '18 at 17:32
  • $\begingroup$ @kasperd: I'd be curious to here this. To verify a factorization, you would need for example the prime factors, and for each prime factor a proof that it is prime. $\endgroup$ – gnasher729 Jan 23 '18 at 22:26
2
$\begingroup$

"How is the traveling salesman problem verifiable in polynomial time?"

Either in the way you describe, or there's not known to be such a way.

"However, what if there is no path that fits this criteria?"

In that case, for all NP machines for the decision problem, the machine will return no for all candidate-certificates.

"How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?"

Well, one could receive an interactive proof that there are no such paths.

The problem you describe, TSP, is not known to be in coNP, so there's not known to be an "NP-like" way of verifying that there is no such path.

|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.