14
$\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?

$\endgroup$
27
$\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).

$\endgroup$
  • 1
    $\begingroup$ Do you mean DNF-Tautology by Taut? Isn't that CoNP-complete? Because CNF-Tautology is trivial. $\endgroup$ – Tayfun Pay Mar 24 '13 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 '13 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 '13 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 '13 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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