On truth-table reducibility to SAT

DOI10.1016/0890-5401(91)90075-DzbMath0800.68443MaRDI QIDQ1173957

Louise Hay, Samuel R. Buss

Publication date: 25 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

SATBoolean circuitsNP- completepolynomial time truth-table reductibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (34)

COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Boolean Game with Prioritized Norms ⋮ Circuit principles and weak pigeonhole variants ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Characterizations of some complexity classes between Θ2p and Δ2p ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Mixed Iterated Revisions: Rationale, Algorithms, and Complexity ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ On quasilinear-time complexity theory ⋮ Isomorphic implication ⋮ On the complexity of entailment in existential conjunctive first-order logic with atomic negation ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy ⋮ Consequences of the provability of NP ⊆ P/poly ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ Planar and grid graph reachability problems ⋮ Knowledge-based programs as succinct policies for partially observable domains ⋮ On the complexity of the clone membership problem ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ The closure of monadic NP ⋮ Unnamed Item ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ On the complexity of data disjunctions. ⋮ On the isomorphism problem for decision trees and decision lists ⋮ On the query complexity of selecting minimal sets for monotone predicates ⋮ Complexity results for explanations in the structural-model approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• More complicated questions about maxima and minima, and some closures of NP
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• A comparison of polynomial time reducibilities
• The difference and truth-table hierarchies for NP
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Relativization of questions about log space computability
• Log Space Recognition and Translation of Parenthesis Languages

This page was built for publication: On truth-table reducibility to SAT