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.