Home

On the Power of Parity Polynomial Time

Jin-yi Cai; Lane A. Hemachandra

Title:
On the Power of Parity Polynomial Time
Author(s):
Cai, Jin-yi
Hemachandra, Lane A.
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-274-87
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:
234
Metadata:
text | xml
Suggested Citation:
Jin-yi Cai, Lane A. Hemachandra, 1987, On the Power of Parity Polynomial Time, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:11844.

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