Content deleted Content added
No edit summary |
Reverted 1 edit by 14.139.238.2 (talk): Unexplained removal of material and references. (TW) |
||
Line 43:
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 reducibilities are used in other contexts of computational complexity theory where other resource bounds are of interest.
== Reductions weaker than Turing reducibility ==
Although Turing reducibility is the most general reducibility that is effective, weaker reducibility relations are commonly studied. These reducibilities are related to relative definability of sets over arithmetic or set theory. They include:
* [[Arithmetical reducibility]]: A set ''A'' is arithmetical in a set ''B'' if ''A'' is definable over the standard model of Peano arithmetic with an extra predicate for ''B''. Equivalently, according to [[Post's theorem]], ''A'' is arithmetical in ''B'' if and only if ''A'' is Turing reducible to <math>B^{(n)}</math>, the ''n''th [[Turing jump]] of ''B'', for some natural number ''n''. The [[arithmetical hierarchy]] gives a finer classification of arithmetical reducibility.
* [[Hyperarithmetical reducibility]]: A set ''A'' is hyperarithmetical in a set ''B'' if ''A'' is <math>\Delta^1_1</math> definable (see [[analytical hierarchy]]) over the standard model of Peano arithmetic with a predicate for ''B''. Equivalently, ''A'' is hyperarithmetical in ''B'' if and only if ''A'' is Turing reducible to <math>B^{(\alpha)}</math>, the ''α''th [[Turing jump]] of ''B'', for some ''B''-[[recursive ordinal]] α.
*[[Constructible universe#Relative constructibility|Relative constructibility]]: A set ''A'' is relatively constructible from a set ''B'' if ''A'' is in ''L''(''B''), the smallest transitive model of [[ZFC set theory]] containing ''B'' and all the ordinals.
== References ==
* K. Ambos-Spies and P. Fejer, 2006. "[http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf Degrees of Unsolvability]." Unpublished preprint.
* P. Odifreddi, 1989. ''Classical Recursion Theory'', North-Holland. ISBN 0-444-87295-7
* P. Odifreddi, 1999. ''Classical Recursion Theory, Volume II'', Elsevier. ISBN 0-444-50205-X
*E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", ''Bulletin of the American Mathematical Society'', volume 50, pages 284–316.
* H. Rogers, Jr., 1967. ''The Theory of Recursive Functions and Effective Computability'', second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
* G Sacks, 1990. ''Higher Recursion Theory'', Springer-Verlag. ISBN 3-540-19305-7
[[Category:Computability theory]]
| |||