Title :
On truth-table reducibility to SAT and the difference hierarchy over NP
Author :
Buss, S.R. ; Hay, Louise
Author_Institution :
Dept. of Math., California Univ., Berkeley, CA, USA
Abstract :
It is shown that polynomial-time truth-table reducibility by 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. It is proved that a constant number of rounds of parallel queries to SAT is equivalent to one round of parallel queries. It is shown that the infinite difference hierarchy over NP is equal to Δp/2, and an oracle separating Δp/2 from the class of predicates polynomial time truth-table reducible to SAT is given
Keywords :
Boolean functions; Turing machines; Boolean circuits; NP; SAT; log-space Turing reducibility; parallel queries; truth-table reducibility; Boolean functions; Circuits; Computer science; Concurrent computing; Finite difference methods; Mathematics; NP-complete problem; Polynomials; Statistics; Turing machines;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5282
