== Reductions stronger than Turing reducibility ==
The strong reducibilities include
*[[many-one reduction|One-one reducibility]]: ''A'' is one-one reducible to ''B'' iffif there is a computable one-one function ''f'' with ''A(x) = B(f(x))'' for all x.
<li>*[[many-one reduction|Many-one reducibility]]: the same''A'' asis onemany-one withoutreducible theto constraint''B'' ofif one-one-nessthere onis 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'' iffif ''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 Turingweak truth-table reducible to ''B'' viaif there is a Turing machinereduction from ''MB'' suchto that''A'' there existsand a recursive function ''f'' sowhich thatbounds ''M''the on[[Turing_reduction#The_use_of_a_reduction|use]]. inputWhenever ''xA'' neveris queriestruth-table ''B''reducible at anyto ''y > f(x)B''. One can show that, ''A'' is also weak truth-table reducible to ''B'', iffsince thereone arecan computableconstruct functionsa ''f''recursive andbound ''g''on suchthe thatuse ''A(x)by =considering g(x,B(0),B(1),...,B(f(x)))'',the hencemaximum wheneveruse ''A''on isany truth-tableoracle, reduciblewhich tois ''B''computable thenif ''A''the reduction is alsototal weakon truth-tableall reducible to ''B''oracles.
*Positive reducible: ''A'' is positive reducible to ''B'' iff ''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.
