Journal article:

    Samuel R. Buss and Louise Hay.
    "On truth-table reducibility to SAT."
    Information and Computation 91 (1991) 86-102.

    Download article: postscript or PDF

    Abstract: We show that polynomial time truth-table reducibility via Boolean circuits to SAT is the same as log space truth-table reducibility via Boolean formulas to SAT and the same as log space Turing reducibility to SAT. In addition, we prove that a constant number of rounds of parallel queries to SAT is equivalent to one round of parallel queries. Finally, we show that the infinite difference hierarchy over NP is equal to $\Delta_2^p$ and give an oracle oracle separating $\Delta_2^p$ from the class of predicates polynomial time truth-table reducible to SAT.

    Earlier conference proceedings article: Truth-table reducibility to SAT and the difference hierarchy over NP in Structure in Complexity, 1986.

Back to Sam Buss's publications page.