Search the Kids Internet
Encyclopedia > Polynomial-time Turing reduction
Article Content
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[?].
All Wikipedia text is available under the terms of the GNU Free Documentation License
|
Search Encyclopedia
|
Featured Article
|