Truth table reduction

In computability theory, a truth table reduction is a reduction from one set of natural numbers to another. Truth table reductions are less powerful than Turing reductions, since not every Turing reduction between sets can be performed by a truth table reduction, but every truth table reduction can be performed by a Turing reduction. A weak truth table reduction is a related type of reduction which is so named because it weakens the constraints placed on a truth table reduction, and provides a weaker equivalence classification; as such, a "weak truth table reduction" can actually be more powerful than a truth table reduction, and perform a reduction which is not performable by truth table.

A Turing reduction from a set "B" to a set "A" computes the membership of a single element in "A" by asking questions about the membership of various elements in "B" during the computation; it may adaptively determine which questions it asks based upon answers to previous questions. In contrast, a truth table reduction or a weak truth table reduction must present all of its (finitely many) oracle queries at the same time. In a truth table reduction, the reduction also gives a boolean function (a truth table) which, when given the answers to the queries, will produce the final answer of the reduction. In a weak truth table reduction, the reduction uses the oracle answers as a basis for further computation which may depend on the given answers but may not ask further questions of the oracle.

Equivalently, a weak truth table reduction is a Turing reduction for which the use of the reduction is bounded by a computable function. For this reason, they are sometimes referred to as bounded Turing (bT) reductions rather than as weak truth table (wtt) reductions.

Properties

As every truth table reduction is a Turing reduction, if "A" is truth table reducible to "B" ("A" &le;tt "B"), then "A" is also Turing reducible to "B" ("A" &le;T "B"). Considering also many-one reducibility and weak truth table reducibility, one gets the following chain of implications:
* $A leq_m B Rightarrow A leq_\left\{tt\right\} B Rightarrow A leq_\left\{wtt\right\} B Rightarrow A leq_T B$; many-one reducibility implies truth table reducibility, which in turn implies weak truth table reducibility, which in turn implies Turing reducibility.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… …   Wikipedia

• Reduction (complexity) — Example of a reduction from a boolean satisfiability problem to a vertex cover problem. Blue vertices form a vertex cover which corresponds to truth values. In computability theory and computational complexity theory, a reduction is a… …   Wikipedia

• Table (information) — Tabular redirects here. For the typewriter key, see tab key. For sortable tables in Wikipedia, see Help:Sorting An example table rendered in a web browser using HTML. A table is a means of arranging data in rows an …   Wikipedia

• Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

• Leibniz: truth, knowledge and metaphysics — Nicholas Jolley Leibniz is in important respects the exception among the great philosophers of the seventeenth century. The major thinkers of the period characteristically proclaim the need to reject the philosophical tradition; in their… …   History of philosophy

• List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

• Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

• Propositional formula — In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional… …   Wikipedia

• Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia