patternMinor
FP^NP-complete problems
Viewed 0 times
completeproblemsstackoverflow
Problem
Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?
Solution
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.
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.
Context
StackExchange Computer Science Q#38150, answer score: 5
Revisions (0)
No revisions yet.