3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Note that research level questions are fine on CS.SE as well. $\endgroup$
    – Juho
    Commented Feb 9, 2015 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.