Reduction (computability theory): Difference between revisions

Revision as of 01:55, 17 July 2007

Revision as of 23:27, 7 August 2007

Line 28:

*[[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 reducton|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'' iffif 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.

*Conjunctive reducibility: Similar to positive reducibility with the additional constraint that only and's are permitted.

*Linear reducibility: Similar to positive reducibility but with the constraint that all atoms of the form ''B(n)'' are combined by exclusive or's. In other words, ''A'' is linear reducible to ''B'' iffif and only if a computable function computes for each ''x'' a finite set ''F(x)'' given as an explicit list of numbers such that ''x ∈ A'' iffif and only if ''F(x)'' contains an odd number of elements of ''B''.

Many of these were introduced by Post (1944). They have since been the subject of much research, and many relationships between them are known.

=== Bounded reducibilities ===

A '''bounded''' form of each of the above strong reducibilities can be defined. The most famous of these is bounded truth-table reduction, but there are also bounded Turing, bounded weak truth-table and others. These first three are the most common ones and they are based on the number of queries. For example, a set ''A'' is bounded truth-table reducible to ''B'' iffif and only if the Turing machine ''M'' computing ''A'' relative to ''B'' computes a list of up to ''n'' numbers, queries ''B'' on these numbers and then terminates for all possible oracle answers; the value ''n'' is a constant independent of ''x''. The difference between bounded weak truth-table and bounded Turing reduction is that in the first case, the up to ''n'' queries have to be made at the same time while in the second case, the queries can be made one after the other. For that reason, there are cases where ''A'' is bounded Turing reducible to ''B'' but not weak truth-table reducible to ''B''.

=== Strong reductions in computational complexity ===