Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
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

4 Answers 4

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?

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer
+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
@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. –  Or Sattath 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.

share|cite|improve this answer
An NP-complete language is, by definition, complete under Karp reductions, so what does the first sentence mean? –  Emil Jeřábek Aug 28 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. –  Mohammad Al-Turkistany Aug 28 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. –  Emil Jeřábek Aug 28 at 16:43
@EmilJeřábek Read carefully section 6.3. I am afraid that skimming is not enough in this case :) –  Mohammad Al-Turkistany Aug 28 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 at 18:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.