On the Power of Probabilistic Polynomial Time: PNP[log] ⊆ PP
Lane A. Hemachandra, Gerd Wechsung · 1988
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.