Editing Polynomial-time reduction (section)

===Truth-table reductions===
A polynomial-time [[truth-table reduction]] from a problem ''A'' to a problem ''B'' (both decision problems) is a polynomial time algorithm for transforming inputs to problem ''A'' into a fixed number of inputs to problem ''B'', such that the output for the original problem can be expressed as a function of the outputs for ''B''. The function that maps outputs for ''B'' into the output for ''A'' must be the same for all inputs, so that it can be expressed by a [[truth table]]. A reduction of this type may be denoted by the expression <math>A \le_{tt}^P B</math>.<ref>{{citation
 | last1 = Buss | first1 = S.R. | author1-link = Samuel Buss
 | last2 = Hay | first2 = L.
 | contribution = On truth-table reducibility to SAT and the difference hierarchy over NP
 | doi = 10.1109/SCT.1988.5282
 | pages = 224–233
 | title = Proceedings of Third Annual Structure in Complexity Theory Conference
 | year = 1988| isbn = 978-0-8186-0866-7 | citeseerx = 10.1.1.5.2387 }}.</ref>