---
tag: 6EKNWDARWZ
kind: concept
name: Truth-table reduction
aliases: [bounded-turing-reduction, tt-reduction, weak-truth-table-reduction, wtt-reduction]
sources:
  - wikipedia: en:2695407@r1336381539
    locator: Truth-table reduction
    note: adopted
    mention: wikipedia://en/2695407
    sections: [Summary]
same_as:
  wikidata: Q7848253
  wikipedia: Truth-table reduction
inventory: [6TJJSXTM50]
---

## Summary

In computability theory, a **truth-table reduction** is a type of reduction from a decision problem $A$ to a decision problem $B$. To solve a problem in $A$, the reduction describes the answer to $A$ as a [[boolean formula|0A58THH5XV]] or [[truth table|05RSK4Q657]] of some finite number of queries to $B$.