patternMinor
Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?
Viewed 0 times
tspthepolynomialverifiabletimebeenhasoptimizationthatproven
Problem
The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in polynomial time. But is there a proof of whether or not it can be verified in polynomial time assuming P ≠ NP?
Solution
If $optTSP$ is in $NP$, then $coNP = NP$. The latter is unresolved currently.
Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to verify a solution to $optTSP$ was minimal, and then comparing the value of that solution to the desired bound). And because $TSP$ is $NP$-complete then this implies $NP = coNP$.
Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to verify a solution to $optTSP$ was minimal, and then comparing the value of that solution to the desired bound). And because $TSP$ is $NP$-complete then this implies $NP = coNP$.
Context
StackExchange Computer Science Q#20204, answer score: 6
Revisions (0)
No revisions yet.