Home

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

Lane A. Hemachandra; Gerd Wechsung

Title:
On the Power of Probabilistic Polynomial Time: PNP[log] ⊆ PP
Author(s):
Hemachandra, Lane A.
Wechsung, Gerd
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-372-88
Abstract:
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.
Subject(s):
Computer science
Item views:
59
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use