On truth-table reducibility to SAT and the difference hierarchy over NP

1 January 1988

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 224-233
https://doi.org/10.1109/sct.1988.5282

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 Delta p/2, and an oracle separating Delta p/2 from the class of predicates polynomial time truth-table reducible to SAT is given.

Keywords

POLYNOMIALS
CIRCUITS
MATHEMATICS
TURING MACHINES
BOOLEAN FUNCTIONS
NP-COMPLETE PROBLEM
STATISTICS
COMPUTER SCIENCE
CONCURRENT COMPUTING
FINITE DIFFERENCE METHODS

This publication has 0 references indexed in Scilit: