0
$\begingroup$

Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?

$\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
2
$\begingroup$

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.

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