Reduction (computability theory): Difference between revisions

Revision as of 19:38, 26 April 2007

Revision as of 11:40, 10 June 2007

Line 40:

{{main|Reduction (complexity)}}

The strong reductions listed above restrict the manner in which oracle information can be accessed by a decision procedure but do not otherwise limit the computational resources available. Thus if a set ''A'' is [[computable set|decidable]] then ''A'' is reducible to any set ''B'' under any of the strong reducibility relations listed above, even if ''A'' is not polynomial-time or exponential-time decidable. This is acceptable in the study of recursion theory, which is interested in theoretical computability, but isit is not reasonable for [[computational complexity theory]], which studies which sets can be decided under certain asymptotical resource bounds.

The most common reducibility in computational complexity theory is [[Polynomial-time reduction|polynomial-time reducibility]]; a set ''A'' is polynomial-time reducible to a set ''B'' if there is a polynomial-time function ''f'' such that for every ''n'', ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''. This reducibility is, essentially, a resource-bounded version of many-one reducibility. Other resource-bounded reducibilites are used in other contexts of omputationalcomputational complexity theory where other resource bounds are of interest.

== Reductions weaker than Turing reducibility ==