Truth-table reduction¶

Reduce membership in one decision problem to a finite, nonadaptive batch of oracle queries whose answer bits are combined by an input-computable Boolean truth table.

Version: v2 · 2026-08-30 · History
Domain-specific #: 3009
Origin domain: computability theory
Subdomain: reducibility and degree structures

Core Idea¶

A set \(A\) is truth-table reducible to \(B\), written \(A\leq_{tt}B\), when one effective total procedure maps each input \(x\) to finitely many queries about \(B\) and a Boolean function such that the function of those simultaneously determined answer bits equals the characteristic value of \(A(x)\). All queries and the answer-combining table are computed from the source input alone, the oracle supplies their membership bits without changing the query set, and the declared Boolean rule produces the source answer; nonadaptivity is the decisive separation from a general Turing reduction.

Scope of Application¶

Truth-table reduction applies when the analyst can specify two sets or decision problems over an effective domain, a computable query generator, a finite list of oracle questions fixed before any answer is seen, and an input-dependent Boolean combination rule and establish that for every source input, a finite oracle-use pattern and Boolean output rule are effectively determined before oracle answers arrive, the computation is total, and the rule returns the correct source membership bit. The entry locks classical computability-theory truth-table reducibility. Complexity-bounded nonadaptive reductions require resource bounds and belong to a separately qualified setting.

Clarity¶

A clear claim names the carrier, governing rule, assumptions, and recognition test. This matters because the source and oracle letters are often swapped across authors, and weak truth-table reduction sounds weaker while actually permits reductions unavailable to strict truth-table form. The disciplined statement is that the object counts as Truth-table reduction exactly when for every source input, a finite oracle-use pattern and Boolean output rule are effectively determined before oracle answers arrive, the computation is total, and the rule returns the correct source membership bit

Manages Complexity¶

The abstraction compresses single-query special cases, bounded truth-table reductions, uniform table encodings, total-functional characterizations, reducibility on sets and languages, and degree structures into a stable carrier, rule, invariant, and failure boundary. It makes comparison tractable while retaining the variables that control validity.

Compression can hide assumptions. A responsible use therefore declares reduction direction, query count, query computability, adaptivity, Boolean combiner, totality, oracle-use bound, uniformity, composition, and induced degree equivalence and returns to the full diagnostic whenever a convention or boundary case changes.

Abstract Reasoning¶

Type the carrier. Establish two sets or decision problems over an effective domain, a computable query generator, a finite list of oracle questions fixed before any answer is seen, and an input-dependent Boolean combination rule and reject examples from a different problem. 2. Lock the rule. Express that for every source input, a finite oracle-use pattern and Boolean output rule are effectively determined before oracle answers arrive, the computation is total, and the rule returns the correct source membership bit independently of one notation or implementation.

Knowledge Transfer¶

Transfer within computability theory is strong when new cases preserve the same carrier, mechanism, and diagnostic. The move from A many-one reduction is a special truth-table reduction that asks one query and returns that bit, possibly with a fixed negation convention if allowed by the chosen formulation. to A total Turing functional on Cantor space gives a truth-table reduction because compactness of \(2^\omega\) yields, for each input, a finite uniform amount of oracle information sufficient to determine the output. demonstrates that continuity.

Relationships to Other Abstractions¶

Current abstraction Truth-table reduction Domain-specific

Parents (1) — more general patterns this builds on

Truth-table reduction is a kind of Algorithm Prime

The proposed strict upward parent is prime:algorithm.

Hierarchy paths (2) — routes to 2 parentless roots

Truth-table reduction → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Truth-table reduction sits in a moderately populated region (60^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Syntax, Rewriting & Declarative Form (41 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08