Revision as of 12:39, 14 June 2009 edit Skeptical scientist (talk \| contribs) Extended confirmed users 645 edits m →Reductions stronger than Turing reducibility ← Previous edit		Revision as of 12:41, 14 June 2009 edit undo Skeptical scientist (talk \| contribs) Extended confirmed users 645 edits m →Reductions stronger than Turing reducibility Next edit →
Line 24: == Reductions stronger than Turing reducibility == The strong reducibilities include [[many-one reduction\|One-one reducibility]]: ''A'' is one-one reducible to ''B'' if there is a computable [[Injective function\|one-to-one function]] ''f'' with ''A''(''x'') = ''B''(''f''(''x'')) for all ''x''. [[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.

Reduction (computability theory): Difference between revisions