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.