Content deleted Content added
m →Reductions stronger than Turing reducibility: added new reducibility article. enumeration reducibility. |
|||
Line 30:
*[[Truth table reduction|Weak truth-table reducible]]: ''A'' is weak truth-table reducible to ''B'' if there is a Turing reduction from ''B'' to ''A'' and a recursive function ''f'' which bounds the [[Turing reduction#The use of a reduction|use]]. Whenever ''A'' is truth-table reducible to ''B'', ''A'' is also weak truth-table reducible to ''B'', since one can construct a recursive bound on the use by considering the maximum use over the tree of all oracles, which will exist if the reduction is total on all oracles.
*Positive reducible: ''A'' is positive reducible to ''B'' if and only if ''A'' is truth-table reducible to ''B'' in a way that one can compute for every ''x'' a formula consisting of atoms of the form ''B''(0), ''B''(1), ... such that these atoms are combined by and's and or's, where the and of ''a'' and ''b'' is 1 if ''a'' = 1 and ''b'' = 1 and so on.
*[[Enumeration reducibility]]: Similar to positive reducibility, relating to the effective procedure of [[enumerability]] from ''A'' to ''B.''
*Disjunctive reducible: Similar to positive reducible with the additional constraint that only or's are permitted.
*Conjunctive reducibility: Similar to positive reducibility with the additional constraint that only and's are permitted.
| |||