Academic Commons

Reports

On the Power of Probabilistic Polynomial Time:
PNP[log] ⊆ PP

Hemachandra, Lane A.; Wechsung, Gerd

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

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