1987 Reports
On the Power of Parity Polynomial Time
This paper proves that the complexity class Ef)P, parity polynomial time [PZ83], contains the class of languages accepted by NP machines with few accepting paths. Indeed, Ef)P contains a. broad class of languages accepted by path-restricted nondeterministic machines. In particular, Ef)P contains the polynomial accepting path versions of NP, of the counting hierarchy, and of ModmNP for m > 1. We further prove that the class of nondeterministic path-restricted languages is closed under bounded truth-table reductions.
Subjects
Files
-
cucs-274-87.pdf application/pdf 401 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-274-87
- Published Here
- November 28, 2011