<p>It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions". </p>

<p>Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (not just decision problems). Although the original definition of both $\mathsf{NP}$-hardness and $\mathsf{NP}$-completeness used Cook reductions (polynomial-time Turing reductions) it has become uncommon to use Cook reductions for $\mathsf{NP}$-completeness (unless it is stated explicitly). I don't recall any recent paper that has used $\mathsf{NP}$-complete to mean $\mathsf{NP}$-complete w.r.t. Cook reductions. (As a side note the first problem that to be proven to $\mathsf{NP}$-hard was TAUT not SAT and the completeness for SAT is implicit in that proof.)</p>

<p>Now if you look at section 7 of the paper, bottom of page 195, you will see that they mean $\mathsf{NP}$-hardness w.r.t. Turing reductions.</p>

<p>So what they mean here is that the problem is in $\mathsf{NP}$, is hard for $\mathsf{NP}$ w.r.t. Cook reductions, but it is unknown to be hard for $\mathsf{NP}$ w.r.t. Karp reductions (polynomial-time many-one reductions).</p>

CC BY-SA 3.0
2013-03-24T16:44:49.133Z
Do you mean DNF-Tautology by Taut? Isn't that CoNP-complete? Because CNF-Tautology is trivial.
Tayfun Pay
CC BY-SA 3.0
2013-03-24T16:58:01.987Z
@TayfunPay: Most likely Tautology for arbitrary formulas not just CNF or DNF. And Co-NP-complete and NP-complete is the same w.r.t. Cook-reductions, which is the reason Kaveh mentions this anecdote.
frafl
CC BY-SA 3.0
2013-03-24T20:36:40.223Z
@Tayfun, Cook proves it for general formulas and uses it DNF-TAUT is a corollary in the paper. Both are NP-*hard* w.r.t. Cook reductions.
Kaveh
CC BY-SA 3.0
2013-03-24T20:37:59.680Z
@frafl, "NP-complete" is defined in [Karp's 1972 paper](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf). [Cook's 1971 paper](http://www.cs.toronto.edu/~sacook/homepage/1971.pdf) defines Cook reductions and proves that TAUT is NP-hard w.r.t. them. It also proves that a number of problems are equivalent w.r.t. Cook reductions. However NP-compelteness is not  explicitly stated in the original paper.
Kaveh
CC BY-SA 3.0
2013-03-23T19:00:41.657Z
2013-03-24T00:15:20.063Z
2013-03-24T00:15:20.063Z
Kaveh
<p>For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. </p>

<p>However, in the famous paper <a href="http://oai.cwi.nl/oai/asset/10046/10046A.pdf">"The ellipsoid method and its consequences in combinatorial optimization"</a>, the authors claim that the fractional chromatic number problem belongs to NP and is NP-hard, yet is not known to be NP-complete. On the third page of the paper, the authors write:</p>

<blockquote>
  <p>... we note that the vertex-packing problem of a graph is in a sense equivalent to the fractional chromatic number problem, and comment on the phenomenon that this latter problem is an example of a problem in $\mathsf{NP}$ which is $\mathsf{NP}$-hard but (as for now) not known to be $\mathsf{NP}$-complete.</p>
</blockquote>

<p>How is this possible? Am I missing a subtle detail in the definition of NP-complete?</p>

<cc.complexity-theory><np-hardness><complexity-classes><terminology>
How can a problem be in NP, be NP-hard and not NP-complete?
Austin Buchanan
# How can a problem be in NP, be NP-hard and not NP-complete?

(Asked by: username_0 on 2013-03-23)

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.

However, in the famous paper ["The ellipsoid method and its consequences in combinatorial optimization"](http://oai.cwi.nl/oai/asset/10046/10046A.pdf), the authors claim that the fractional chromatic number problem belongs to NP and is NP-hard, yet is not known to be NP-complete. On the third page of the paper, the authors write:

> ... we note that the vertex-packing problem of a graph is in a sense equivalent to the fractional chromatic number problem, and comment on the phenomenon that this latter problem is an example of a problem in $\mathsf{NP}$ which is $\mathsf{NP}$-hard but (as for now) not known to be $\mathsf{NP}$-complete.

How is this possible? Am I missing a subtle detail in the definition of NP-complete?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, terminology

---

## 1 answers

### Answer by username_1 on 2013-03-23. Score: 28 | Accepted answer

It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions".

Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (not just decision problems). Although the original definition of both $\mathsf{NP}$-hardness and $\mathsf{NP}$-completeness used Cook reductions (polynomial-time Turing reductions) it has become uncommon to use Cook reductions for $\mathsf{NP}$-completeness (unless it is stated explicitly). I don't recall any recent paper that has used $\mathsf{NP}$-complete to mean $\mathsf{NP}$-complete w.r.t. Cook reductions. (As a side note the first problem that to be proven to $\mathsf{NP}$-hard was TAUT not SAT and the completeness for SAT is implicit in that proof.)

Now if you look at section 7 of the paper, bottom of page 195, you will see that they mean $\mathsf{NP}$-hardness w.r.t. Turing reductions.

So what they mean here is that the problem is in $\mathsf{NP}$, is hard for $\mathsf{NP}$ w.r.t. Cook reductions, but it is unknown to be hard for $\mathsf{NP}$ w.r.t. Karp reductions (polynomial-time many-one reductions).

> **Comments:**
> **username_2**: Do you mean DNF-Tautology by Taut? Isn't that CoNP-complete? Because CNF-Tautology is trivial.  
> **username_3**: @TayfunPay: Most likely Tautology for arbitrary formulas not just CNF or DNF. And Co-NP-complete and NP-complete is the same w.r.t. Cook-reductions, which is the reason Kaveh mentions this anecdote.  
> **username_1**: @Tayfun, Cook proves it for general formulas and uses it DNF-TAUT is a corollary in the paper. Both are NP-*hard* w.r.t. Cook reductions.  
> **username_1**: @frafl, "NP-complete" is defined in [Karp's 1972 paper](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf). [Cook's 1971 paper](http://www.cs.toronto.edu/~sacook/homepage/1971.pdf) defines Cook reductions and proves that TAUT is NP-hard w.r.t. them. It also proves that a number of problems are equivalent w.r.t. Cook reductions. However NP-compelteness is not  explicitly stated in the original paper.  

---

