[Solved]: Can finding a witness be NP-hard even if we already know there is one?

Problem Detail: 

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?

Asked By : mba

Answered By : Rahul Savani

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40507