Technical reports:
On the Power of Probabilistic Polynomial Time: PNP[log] PP
Lane A. Hemachandra; Gerd Wechsung
Downloads:
- Title:
- On the Power of Probabilistic Polynomial Time: PNP[log] PP
- Author(s):
-
Hemachandra, Lane A.
Wechsung, Gerd - Date:
- 1988
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:12055
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-372-88
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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:
- 45