patternMajor
How is the traveling salesman problem verifiable in polynomial time?
Viewed 0 times
salesmanproblemthepolynomialverifiabletimetravelinghow
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#86954, answer score: 36
Revisions (0)
No revisions yet.