Polynomial-time reduction

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 other 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 are more powerful than Karp reductions; for example, any problem in co-NP has a Cook reduction to a problem in NP. While this power is useful for designing reductions, the downside is that classes such as NP are not closed under Cook reductions, and so they are not useful for proving that a problem is in NP. However, they are useful for showing that problems are in P.