1988 Reports
On the Power of Probabilistic Polynomial Time:
PNP[log] ⊆ PP
We show that every set in the ΘP2 level of the polynomial hierarchy -- that is, every set polynomial-time truth-table reducible to SAT -- is accepted by a probabilistic polynomialtime Turing machine: PNP[log] ⊆ PP.
Subjects
Files
-
cucs-372-88.pdf
application/pdf
300 KB
Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-372-88
- Published Here
- December 21, 2011