| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429894 | Journal of Computer and System Sciences | 2008 | 6 Pages |
Abstract
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 . Even showing that the hierarchy collapsed to remained open prior to this paper.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
