Polynomial time reduction
A polynomial time reduction (also known as a polynomial reduction ) is a special form of reduction in theoretical computer science . In addition to the reducibility, it is required here that the reduction can be calculated deterministically in polynomial time.
Polynomially bounded Turing reductions are also called Cook's reduction (according to Stephen A. Cook ) . However, the term polynomial time reduction usually refers to a polynomially restricted many-one reduction (also Karp reduction , after Richard M. Karp ).
Polynomial many-one reductions are used in complexity theory, for example, to prove that a language of complexity class NP is also NP-complete .
Formal definition
Be and two decision problems with .
is polynomially reducible to language if there is a function that can be calculated in polynomial time , so that equivalence applies to all words .
Spellings
There are different spellings, including
swell
- ↑ Th. H. Cormen et al., Algorithmen - An Introduction , MIT Press (2009), ISBN 3486590022 , p. 1077