4 ms·

> NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time. That is (nea

> NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time. That is (nearly) correct under Cook reductions but not Karp reductions. I say "nearly" because "if language L can be solved (decided) in polynomial time, then so can any problem in NP" is a vacuously true statement for any L not in P, so by this definition nearly all languages (a measure 1 fraction of them) are also NP-complete despite most of them not being in any particularly interesting complexity class. If we escape this degeneracy by replacing the antecedent with "given access to an efficient way to decide L", then we've recreated NP hardness under Cook reductions.

danbruc 4y ago
If I understand this correctly as I mostly read this just today, then Cook reductions - which is the name for polynomial Turing reductions - are the more general class whereas Karp reductions - which are polynomial many-one reductions - are a more restricted class which - to a first approximation - only allows one oracle query and must return the result unmodified. So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions? If I want to finely separate classes of problems, then Karp reductions are probably better suited as the reduction builds a much more direct link between the two problems. That is (nearly) correct under Cook reductions but not Karp reductions. It is however still not clear to me why this is not true under Karp reductions, because there are not necessarily Karp reductions for some problems that have Cook reductions? If so, are there two different NP-complete classes, one per reduction?
- JohnKemeny 4y ago
  > So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions? Because under Karp, SAT and UNSAT are widely different problems whereas under Cook, they're not. You can verify SAT in polynomial time. You can not do that for UNSAT.

danbruc 4y ago

If I understand this correctly as I mostly read this just today, then Cook reductions - which is the name for polynomial Turing reductions - are the more general class whereas Karp reductions - which are polynomial many-one reductions - are a more restricted class which - to a first approximation - only allows one oracle query and must return the result unmodified. So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions? If I want to finely separate classes of problems, then Karp reductions are probably better suited as the reduction builds a much more direct link between the two problems. That is (nearly) correct under Cook reductions but not Karp reductions. It is however still not clear to me why this is not true under Karp reductions, because there are not necessarily Karp reductions for some problems that have Cook reductions? If so, are there two different NP-complete classes, one per reduction?

JohnKemeny 4y ago
> So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions? Because under Karp, SAT and UNSAT are widely different problems whereas under Cook, they're not. You can verify SAT in polynomial time. You can not do that for UNSAT.