Reduction (computability theory): Difference between revisions

Revision as of 23:08, 24 September 2007

Revision as of 23:09, 24 September 2007

Line 27:

*[[many-one reduction|Many-one reducibility]]: ''A'' is many-one reducible to ''B'' if there is a computable function ''f'' with ''A''(''x'') = ''B''(''f''(''x'')) for all ''x''.

*[[Truth table reduction|Truth-table reducible]]: ''A'' is truth-table reducible to ''B'' if ''A'' is Turing reducible to ''B'' via a single (oracle) Turing machine which produces a total function relative to every oracle.

*[[Truth table reductonreduction|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 on any oracle, which is computable 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.

*Disjunctive reducible: Similar to positive reducible with the additional constraint that only or's are permitted.