Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It is better to make your question self-contained by including (some of) the relevant definitions, or links to Wikipedia $\endgroup$ – 6005 Jun 13 '20 at 22:13
Add a comment
|
$\begingroup$
$\endgroup$
It has been proven that TSP is $FP^{NP}$-complete but it remains an open question whether TSP is a function problem in $FNP$ (it probably is not). The reason is that, in the case of TSP, the optimal solution is not an adequate certificate, as we do not know how to verify in polynomial time that it is optimal.
You can see a proof that TSP is $FP^{NP}$-complete here, starting on page 418.
Note: I don't know if it's allowed to put the link to that PDF although it's from a university. You can buy the full book searching for Computational Complexity by Christos H. Papadimitriou.
