Polynomial-time reduction

From Wikipedia, the free encyclopedia

In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction. If it is a Turing reduction, it is called a polynomial-time Turing reduction or Cook reduction.

Polynomial-time reductions are important and widely-used because they are powerful enough to perform many transformations between important problems, but still weak enough that polynomial-time reductions from problems in NP or co-NP to problems in P are considered unlikely to exist. This notion of reducibility is used in the standard definitions of several complete complexity classes, such as NP-complete, PSPACE-complete and EXPTIME-complete.

Within the class P, however, polynomial-time reductions are inappropriate, because any problem in P can be polynomial-time reduced (both many-one and Turing) to any non-trivial problem in P. Thus, for classes within P such as L, NL, NC, and P itself, log-space reductions are used instead.

If a problem has a Karp reduction to a problem in NP, this shows that the problem is in NP. Cook reductions seem to be more powerful than Karp reductions; for example, any problem in co-NP has a Cook reduction to any NP-complete problem, whereas any problems that are in co-NP - NP (assuming they exist) will not have Karp reductions to any problem in NP. While this power is useful for designing reductions, the downside is that certain classes such as NP are not known to be closed under Cook reductions (and are widely believed not to be), so they are not useful for proving that a problem is in NP. However, they are useful for showing that problems are in P and other classes that are closed under such reductions.