Reduction (computability theory): Difference between revisions

Revision as of 07:12, 26 January 2009

Revision as of 20:13, 10 June 2009

Line 32:

*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'' if 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'' if and only if ''F''(''x'') contains an odd number of elements of ''B''.

Many of these were introduced by Post (1944). Post was searching for a non-[[recursive|recursive set]] [[recursively enumerable]] set which the [[halting problem]] could not be Turing reduced to. As he could not construct such a set in 1944, he instead worked on the analogous problems for the various reducibilities that he introductedintroduced. These reducibilities have since been the subject of much research, and many relationships between them are known.

=== Bounded reducibilities ===