Problem Detail: 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?
Asked By : Mehrdad
Answered By : Scrub
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$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/20204 Ask a Question Download Related Notes/Documents
