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

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Wheatley Heights, New York

... the town the population is spread out with 30.3% under the age of 18, 8.1% from 18 to 24, 29.9% from 25 to 44, 23.8% from 45 to 64, and 7.9% who are 65 years of age ...

 
 
 
This page was created in 22.8 ms