Conference proceedings article:
Samuel R. Buss and Louise Hay.
"On truth-table reducibility to SAT and the difference hierarchy over NP."
In Proceedings of the the IEEE Structure in Complexity Conference, IEEE Computer Society Press, 1988, pp. 224-233.
Download article: postscript or PDF.
Abstract: We show that polynomial time truth-table reducibility via Boolean circuits to SAT is the same as logspace truth-table reducibility via Boolean formulas to SAT and the same as logspace 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. We give an oracle relative to which $\Delta^p_2$ is not equal to the class of predicates polynomial time truth-table reducible to SAT.
Later journal article: Truth-table reducibility to SAT in Information and Computation, 1991. (Contains many of the results from the conference version)
Back to Sam Buss's publications page.