Polynomial time reduction

from Wikipedia, the free encyclopedia

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 .


There are different spellings, including


  1. Th. H. Cormen et al., Algorithmen - An Introduction , MIT Press (2009), ISBN 3486590022 , p. 1077