<p>You may be interested in the $k$-creative sets, invented in <a href="ftp://ftp.cs.wisc.edu/pub/techreports/1984/TR533.pdf">[1]</a> as a conjectured counterexample to the <a href="http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture">Berman-Hartmanis conjecture</a> that all NP-complete sets are isomorphic to SAT.</p>

<p>"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.</p>

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

CC BY-SA 3.0
2012-12-21T20:02:31.587Z
2012-12-21T20:02:31.587Z
SamM
<p>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.</p>

<p>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.).</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-03-14T14:53:25.223Z
+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
CC BY-SA 3.0
2013-03-24T16:46:26.697Z
@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
CC BY-SA 3.0
2013-03-14T09:10:29.953Z
2013-03-14T09:10:29.953Z
Or Sattath
<p>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.</p>

<p>M.Agrawal,S.Biswas, <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=215395" rel="nofollow">Universal relations</a> in Proceedings IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207–220.</p>

CC BY-SA 3.0
2015-08-28T16:20:38.370Z
An NP-complete language is, by definition, complete under Karp reductions, so what does the first sentence mean?
Emil Jeřábek
CC BY-SA 3.0
2015-08-28T16:35:02.810Z
@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
CC BY-SA 3.0
2015-08-28T16:43:29.313Z
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
CC BY-SA 3.0
2015-08-28T16:56:46.713Z
@EmilJeřábek Read carefully section 6.3. I am afraid that skimming is not enough in this case :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-28T18:09:14.073Z
@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
CC BY-SA 3.0
2015-08-29T05:08:33.837Z
Please add a link to the paper. The copy I found has no section 6.3.
Kaveh
CC BY-SA 3.0
2015-08-29T06:15:06.743Z
@Kaveh Added the requested link.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-29T08:15:18.000Z
@Kaveh Sorry, fixed it.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-28T15:15:08.967Z
2015-08-29T08:15:34.457Z
2015-08-29T08:15:34.457Z
Mohammad Al-Turkistany
<p>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.</p>

<p>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.</p>

<hr>

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

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

<p>$$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$$</p>

<p>which means</p>

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

<p>And by Cook's theorem this is equivalent to</p>

<p>$$ SAT \leq^\mathsf{P}_m A$$</p>

<p>which means </p>

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

<p>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. </p>

<p>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 <a href="http://plato.stanford.edu/entries/intuitionistic-logic-development/">this</a>).</p>

<p>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?</p>

CC BY-SA 3.0
2012-12-21T20:00:04.307Z
Why? Does a P-time algorithm for an intermediate problem imply P=NP?
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-12-21T20:02:27.683Z
@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
CC BY-SA 3.0
2012-12-21T19:50:11.843Z
2013-02-04T22:44:46.403Z
2013-02-04T22:44:46.403Z
Kaveh
<p>Is there any $L\in {\bf NP}$ with the following properties:</p>

<ol>
<li><p>It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.</p></li>
<li><p>There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\bf NP}$-complete problem) to $L$.</p></li>
</ol>

<p>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? </p>

CC BY-SA 3.0
2012-12-21T21:50:02.963Z
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
<cc.complexity-theory><np-hardness><reductions>
Does NP-completeness/hardness have to be constructive?
Andras Farago
# Does NP-completeness/hardness have to be constructive?

(Asked by: username_0 on 2012-12-21)

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?

**Tags:** cc.complexity-theory, np-hardness, reductions

> **Comments:**
> **username_1**: It seems to me that the title and body ask two different questions. For example, username_4's answer works for the question in the body, but not for the question in the title.  

---

## 4 answers

### Answer by username_4 on 2012-12-21. Score: 15 | Accepted answer

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](http://plato.stanford.edu/entries/intuitionistic-logic-development/)).

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?

> **Comments:**
> **username_5**: Why? Does a P-time algorithm for an intermediate problem imply P=NP?  
> **username_4**: @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.  

---

### Answer by username_2 on 2012-12-21. Score: 12

You may be interested in the $k$-creative sets, invented in [[1]](ftp://ftp.cs.wisc.edu/pub/techreports/1984/TR533.pdf) as a conjectured counterexample to the [Berman-Hartmanis conjecture](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_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 by username_3 on 2013-03-14. Score: 6

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.

> **Comments:**
> **username_4**: +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.)  
> **username_3**: @username_4 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.  

---

### Answer by username_5 on 2015-08-28. Score: 2

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](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=215395) in Proceedings IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207–220.

> **Comments:**
> **username_6**: An NP-complete language is, by definition, complete under Karp reductions, so what does the first sentence mean?  
> **username_5**: @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.  
> **username_6**: 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.  
> **username_5**: @EmilJeřábek Read carefully section 6.3. I am afraid that skimming is not enough in this case :)  
> **username_7**: @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.  
> **username_4**: Please add a link to the paper. The copy I found has no section 6.3.  
> **username_5**: @username_4 Added the requested link.  
> **username_5**: @username_4 Sorry, fixed it.  

---

