Does NP-completeness/hardness have to be constructive?

Question

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?

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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.