patternMinor
Can finding a witness be NP-hard even if we already know there is one?
Viewed 0 times
canknowhardwitnessalreadyonefindingeventhere
Problem
The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand.
Suppose that we have a problem in which the we know the answer is yes, furthermore we can verify a witness in polynomial time.
Can we then always find a witness in polynomial time? Or can this "search problem" be NP-hard?
Suppose that we have a problem in which the we know the answer is yes, furthermore we can verify a witness in polynomial time.
Can we then always find a witness in polynomial time? Or can this "search problem" be NP-hard?
Solution
TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.
There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:
Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L
and the references [6] and [11] within. PDF available here.
There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:
Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L
and the references [6] and [11] within. PDF available here.
Context
StackExchange Computer Science Q#40507, answer score: 6
Revisions (0)
No revisions yet.