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

Question

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?

Answer 1

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.

Answer 2

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 [1] (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.

---

[1] Khanna, Sanjeev, Nathan Linial, and Shmuel Safra. "On the hardness of approximating the chromatic number." Theory and Computing Systems, 1993., Proceedings of the 2nd Israel Symposium on the. IEEE, 1993.

Answer 3

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 \;$.

Answer 4

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

Answer 5

Here's a simple argument that the ability to find a witness in polynomial time would imply P=NP:

1. Assume that we have a poly-time algorithm for finding a witness to any YES-instance of some NP-complete problem. Then there exist absolute constants $k$ and $c$ such that when run on a valid input of size $n$, the algorithm completes after at most $n^k + c$ steps and reports a valid witness. (Note that on an invalid input -- specifically, a NO-instance -- the algorithm's behaviour is undefined. It may detect a contradiction and abort, or produce an invalid witness, or even loop forever.)
2. Analyse the algorithm to derive concrete values for $k$ and $c$. (Loose upper bounds are fine.)
3. To solve an arbitrary instance of the problem in poly-time:
   1. Guess that the instance is a YES-instance, and run the poly-time witness-finding algorithm on it for at most $n^k+c+1$ steps.
   2. If the algorithm aborts early, or runs for $n^k+c+1$ steps, report "NO".
   3. Otherwise check the witness it produced. This can be done in poly-time. If the witness is valid, report "YES", otherwise report "NO".