Polynomial-time reduction

A Polynomialzeitreduktion (also polynomial reduction) is a special form of reduction in theoretical computer science. In addition to the reducibility is required here is that the reduction can be computed in deterministic polynomial time.

Polynomial- time Turing reductions are referred to ( according to Stephen A. Cook) as a Cook reduction. Mostly, however, the term refers to a Polynomialzeitreduktion polynomially bounded many-one reduction ( also Karp - reduction, by Richard M. Karp ).

Polynomial many-one reductions are used in complexity theory, for example, to prove that a language of complexity class NP is NP -complete.

Spellings

There are different spellings, including

• Complexity Theory