# 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. 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? 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. Dec 21 '12 at 20:02

You may be interested in the $k$-creative sets, invented in  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.

 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.

The following is an example for the question in the title. It is taken from the following paper: Jan Kratochvil, Petr Savicky, and Zsolt Tuza. One more occurrence of variables makes satisfiability jump from trivial to np-complete. SIAM Journal on Computing, 22(1):203–210, 1993.

Let f(k) be the maximal integer r such that every k-SAT forumula in which each variable occurs at most r times, is satisfiable. It is not known whether f(k) is computable, although relatively tight bounds are known for it (see H. Gebauer, R. Moser, D. Scheder, and E. Welzl. The Lov ́asz Local Lemma and Satisfiability. Efficient Algorithms, pages 30–54, 2009.).

(k,s)-SAT is the problem k-SAT restricted to the forumlas in which each variable occurs at most s times.

Kratochvil et al. proved that (k,f(k)+1)-SAT is NP-complete. Note that (k,f(k))-SAT problems are always satisfiable (by definition). The reduction itself is non-constructive: note that the reduction outputs a formula in which each variable occurs at most f(k)+1 times, even though f(k) is not known to be computable. The main non-constructive idea is that even though the value f(k) is unknown, there exists a (k,f(k)+1)-SAT formula which is non-satisfiable, and they manipulate that formula according to their needs.

• +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.) Mar 14 '13 at 14:53
• @Kaveh Indeed the reduction is not computable, but the problem itself is: (k,s)-SAT is clearly in NP for every s. The parameter that makes the problem NP-complete, namely f(k)+1, is the object that is not computable. Mar 24 '13 at 16:46

Agrawal and Biswas presented an NP-complete language for which there is no known Karp or Cook reduction. The proof of completeness follows because its witness relation is universal ( the witness relation has the required join and equivalence operators needed to be universal). The language is given in section 6.3 in the reference.

M.Agrawal,S.Biswas, Universal relations in Proceedings IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207–220.

• An NP-complete language is, by definition, complete under Karp reductions, so what does the first sentence mean? Aug 28 '15 at 16:20
• @EmilJeřábek It means exactly what it says, there is no known Karp or Cook reduction. Agrawal and Biswas proved that Sets with universal relations are NP-complete. I suggest you read the paper. Aug 28 '15 at 16:35
• No, it can’t mean what it says, because what it says makes no sense. Something not known to be complete under Karp reductions is, a fortiori, not known to be NP-complete. I skimmed through the abstract and introduction of the paper, and still didn’t find anything matching your description. Aug 28 '15 at 16:43
• @EmilJeřábek Read carefully section 6.3. I am afraid that skimming is not enough in this case :) Aug 28 '15 at 16:56
• @MohammadAl-Turkistany, I believe the point is that the statements "is not known to be complete under K. reductions" and "there is no known K. reduction" have different meanings. The post says one thing and your comment says the other.
– usul
Aug 28 '15 at 18:09