Proving SAT does not have small circuits with an application to the two queries problem

摘要

We show that if SAT does not have small circuits, then there must exist a small number of satisfiable formulas such that every small circuit fails to compute satisfiability correctly on at least one of these formulas. We use this result to show that if PNP[1]=PNP[2], then the polynomial-time hierarchy collapses to S2p⊆Σ2p∩Π2p. Even showing that the hierarchy collapsed to Σ2p remained open prior to this paper.