Polynomial-time Turing reduction

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.

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.