Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?


TSP is actually OptP-complete and so are many other optimization problems, including Knapsack, MAX-SAT, 0-1 Integer Linear Programming. This class and proof technique is largely the work of Mark Krentel; orig paper STC'86. The journal version of the paper has more details, including the fact that OptP is subclass of FPNP.

LEX-MIN-SAT, finding the lexicographically smallest satisfying assignment, is OptP-complete under metric reductions. There's also an analogue of Schaefer's dichotomy theorem for LEX-MIN-SAT proved by Reith and Vollmer http://arxiv.org/pdf/cs/9809116.pdf

I think is almost a research-level, or at least graduate-level question, by the way.

| cite | improve this answer | |
  • 2
    $\begingroup$ Note that research level questions are fine on CS.SE as well. $\endgroup$ – Juho Feb 9 '15 at 14:05

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.