From Wikipedia, the free encyclopedia.
In computational complexity theory a polynomial-time Turing reduction or Cook reduction of a decision problem L to a decision problem M is an oracle machine that has an oracle for M and can decide L in polynomial time.
If such a reduction exists, then every algorithm for M immediately yields an algorithm for L, with only a modest (i.e. polynomial) slow-down.
The intuitive notion of reducibility can be formalized in different ways: see polynomial-time many-one reduction and logarithmic-space many-one reduction.
