# Can finding a witness be NP-hard even if we already know there is one?

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?

## migrated from cstheory.stackexchange.comMar 17 '15 at 15:08

This question came from our site for theoretical computer scientists and researchers in related fields.

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  and  within. PDF available here.

No, you can't always find a solution in polynomial time, even if you know there is a solution.

According to Khanna, Linial, and Safra  (see the 3rd paragraph), it follows already from the classic 1972 work by Karp that that coloring a 3-colorable graph with 3 colors is NP-hard. (Their work extends this to show that 4-coloring 3-colorable graphs is still NP-hard).

Note that this does not contradict the answer by Rahul Savani. This is because for all binary relations $P$ in FNP, we must be able to verify in polynomial time if $P(x,y)$ is in the relation. Given that deciding if a 3-colorable graph with 3 colors is NP-complete, it is unlikely the problem of finding a 4-coloring in a 3-colorable graph is in FNP since we cannot verify the validity of the input $x$ in polynomial time. Thus, there is no contradiction to the Megiddo-Papadimitriou result.

If an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then $\: NP = coNP \;$.

Proof:

If an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then:

Let $R$ be such a hard relation, and let $M'$ be a yes-answer-only co-nondeterministic polynomial-time Turing reduction from $SAT$ to $R$. $\:$ Let $M$ be the coNP algorithm given by:
$\;$ Attempt to parse the alleged anti-certificate into an inner certificate and responses.
$\;$ If that fails then output YES, else attempt to run $M'$ on the inner anti-certificate by giving
$\;$ the same response as was given before for repeat-queries and using the responses from
$\;$ the (outer) anti-certificate for all other oracle queries. $\:$ If $M'$ would make more distinct
$\;$ queries than the number of responses or any of its queries would not be related by $R$ to
$\;$ that query's response or $M'$ would output YES, the $M$ outputs YES, else $M$ outputs NO.
Since being an oracle for $R$ just imposes independent conditions on the oracle's responses
and $M'$ is a yes-answer-only reduction, the query-response pairs produced by $M'$
and a valid anti-certificate can always be extended to an oracle for $R$, so $M$ solves $SAT\hspace{-0.02 in}$.
Thus $\: SAT\in coNP \;$.
Since $SAT$ is $NP$-hard with respect to deterministic polynomial-time reductions, $\: NP\subseteq coNP \;$.
By symmetry, $\: coNP \subseteq NP \;$. $\;\;\;\;$ Thus $\: NP = coNP \;$.

Therefore, if an NP-relation is NP-hard with respect to yes-answer-only
co-nondeterministic polynomial-time Turing reductions, then $\: NP = coNP \;$.

• I dont understand any of this. Can you define a "yes-answer-only co-nondeterministic polynomial-time Turing reduction", an "anti-certificate", and also clarify what $M'$ is exactly ("reduction from R SAT" makes no sense to me)? – Sasho Nikolov Mar 17 '15 at 5:42
• A "yes-answer-only co-nondeterministic polynomial-time Turing reduction" is a coNP oracle machine whose oracle is for what the reduction is to, such that it will never query the oracle on an input for which there is no polynomial-size string that the query is related to by $R$. $\:$ (continued ...) $\;\;\;\;$ – user12859 Mar 17 '15 at 5:56
• (... continued) $\:$ An anti-certificate is the analogue of a certificate, with YES and NO interchanged. $\:$ $M'$ is the reduction mentioned in the sentence that introduced $M'$. $\:$ (I fixed the typo at the end of that sentence.) $\;\;\;\;$ – user12859 Mar 17 '15 at 5:56

This depends slightly on the precise interpretation of your question, but I think your scenario can be generically described as a problem 'COMPUTE Y' where given some universally fixed polynomial time algorithm $T$ and polynomial $p$, on input $\langle x, 1^n \rangle$, output a string $y \in \{0,1\}^{p(n)}$, such that $T(x,y,1^n)$ outputs 1, and $y$ always exists for all possible $x$.

One question then might be whether a polynomial time algorithm for 'COMPUTE Y' implies $P = NP$

In this case, assume you can solve (say) 3SAT in polynomial time with a constant number of calls to an oracle that solves 'COMPUTE Y', i.e. some algorithm $A$ where $A(\phi) = 1$ iff $\phi$ is satisfiable, $A(\phi)=0$ otherwise. Flip the output bit to get $\bar{A}$, an algorithm where $\bar{A}(\phi) = 0$ iff $\phi$ is satisfiable and $\bar{A}(\phi) = 1$ if $\phi$ is unsatisfiable.

Convert this algorithm $\bar{A}$ (which uses an oracle for 'COMPUTE Y') into a nondeterministic algorithm (that uses no oracles) by simply replacing each oracle call with a nondeterministic guess of $y$ that you can check with a call to $T$. Now you have a nondeterministic algorithm which successfully decides unsatisfiable 3CNF instances, so $NP = coNP$

As an aside, if $NP = coNP$, that implies that all $NP$ complete problems (like $k$-clique or 3SAT) have slight variations whose decision problem is easy (always 'yes') yet whose search version is $NP$-hard