__Conference proceedings article:__

** Samuel R. Buss and Louise Hay.
"On truth-table reducibility to SAT and the difference hierarchy
over NP."
In **

** 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)