15
$\begingroup$

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", 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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
28
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Do you mean DNF-Tautology by Taut? Isn't that CoNP-complete? Because CNF-Tautology is trivial. $\endgroup$
    – Tayfun Pay
    Mar 24, 2013 at 16:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – frafl
    Mar 24, 2013 at 16:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Mar 24, 2013 at 20:36
  • $\begingroup$ @frafl, "NP-complete" is defined in Karp's 1972 paper. Cook's 1971 paper 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. $\endgroup$
    – Kaveh
    Mar 24, 2013 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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