# Does NP-completeness/hardness have to be constructive?

Is there any $L\in {\bf NP}$ with the following properties:

1. It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.

2. There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\bf NP}$-complete problem) to $L$.

In other words, if a polynomial time algorithm for $L$ implies the collapse of ${\bf NP}$ into ${\bf P}$, then is it necessary that this "general hardness" of $L$ for ${\bf NP}$ must be somehow $constructive$, in the sense that, say, $SAT$ must be reducible to $L$ via some specific reduction?

-
It seems to me that the title and body ask two different questions. For example, Kaveh's answer works for the question in the body, but not for the question in the title. –  Robin Kothari Dec 21 '12 at 21:50

Yes, there are such sets, take any $\mathsf{NP}$-intermediate set (any set that is provably $\mathsf{NP}$-intermediate assuming $\mathsf{P}\neq\mathsf{NP}$), e.g. construct one from SAT using Ladner's theorem.

Note that your $L$ needs to considered an $\mathsf{NP}$-intermediate problem, since it is in $\mathsf{NP}$ but not complete for it. Note also that you are assuming that $\mathsf{P}\neq\mathsf{NP}$ otherwise there is no such $L$ as every non-trivial problem would be complete for $\mathsf{NP}$ if $\mathsf{NP}=\mathsf{P}$. Additionally the conditions that you have given does not imply to completeness so the question in the first part is not the same as the question about constructiveness of completeness.

Regarding the question in the title, i.e. "does $\mathsf{NP}$-hardness have to be constructive?".

The answer depends on what we mean by "constructive". Classically, a decision problem $A$ is defined to be $\mathsf{NP}$-hard iff

$$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$$

which means

$$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$$

And by Cook's theorem this is equivalent to

$$SAT \leq^\mathsf{P}_m A$$

which means

$$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in A)$$

How can we make this definition constructive? It is already seems very constructive to me. I guess what you want to ask is if we can prove this for some $A$ without knowing what is $f$ explicitly. I don't remember seeing any such hardness proof.

Classically even when we don't have a specific function there is a function, saying that it is impossible that no function is a reduction is equivalent to saying that some function is a reduction. To talk about constructiveness we need to be more considerate. For example we can talk about statements which are provable classically but not constructively (e.g. intuitionism where different state of mathematical knowledge makes sense, Google for "ideal mathematician" or check this).

Intuitively it seems plausible to me that we can prove such a statement using a proof by contradiction and without giving any explicit reduction function. But it won't mean that there is no constructive proof of the statement. To be say more that no constructive proof exists we have to be more specific: proofs in which theory/system? what do we mean by a constructive proof?

-
Why? Does a P-time algorithm for an intermediate problem imply P=NP? –  Mohammad Al-Turkistany Dec 21 '12 at 20:00
@Mohammad, the definition of an $\mathsf{NP}$-intermediate problem states that it is not in $\mathsf{P}$ and we know that $\mathsf{P}\neq\mathsf{NP}$ implies the problem is $\mathsf{NP}$-intermediate. –  Kaveh Dec 21 '12 at 20:02
+1 Aha, got it. Thanks. –  Mohammad Al-Turkistany Dec 21 '12 at 20:07

You may be interested in the $k$-creative sets, invented in [1] as a conjectured counterexample to the Berman-Hartmanis conjecture that all NP-complete sets are isomorphic to SAT.

"Isomorphic" is different from a Turing reduction (significantly weaker in fact), but these sets were shown to be NP-hard directly and as far as I know there's no known reduction to SAT. That said, by the definition of NP-completeness there must be some reduction between the two, so while this meets the criterion of "no known" reduction it may not be exactly what you're looking for.

[1] Joseph, D. and Young, P. Some remarks on witness functions for nonpolynomial and noncomplete sets in NP. Theoretical Computer Science. vol 39, pg 225--237. 1985. Elsevier.

-
+1. IIUC, what are saying is that a class of problems depending on $k$ are all NP-complete but the reductions are not known to be computable uniformly from $k$. (But also the problems themselves are not uniformly computably enumerable since we don't know how to compute $f(k)$ so it is not surprising that reductions are not uniformly computable.) –  Kaveh Mar 14 '13 at 14:53