Technical reports:
On the Power of Parity Polynomial Time
Jin-yi Cai; Lane A. Hemachandra
Downloads:
- Title:
- On the Power of Parity Polynomial Time
- Author(s):
-
Cai, Jin-yi
Hemachandra, Lane A. - Date:
- 1987
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11844
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-274-87
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 193