On the power of parity polynomial time

DOI10.1007/BF02090768zbMath0718.68038OpenAlexW1982406523MaRDI QIDQ5750401

Jin-Yi Cai, Hemaspaandra, Lane A.

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090768

zbMATH Keywords

computational complexity theoryNP machinesparity polynomial timeinclusions and separations of complexity classesnondeterministic path-restricted languagespath-restricted nondeterministic machines

Mathematics Subject Classification ID

Related Items (33)

A taxonomy of complexity classes of functions ⋮ A complexity theory for feasible closure properties ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ On helping by parity-like languages ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Unambiguous computations and locally definable acceptance types ⋮ Universally serializable computation ⋮ On the power of unambiguity in log-space ⋮ Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ On sets polynomially enumerable by iteration ⋮ THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY ⋮ Modulo classes and logarithmic advice ⋮ Helping by unambiguous computation and probabilistic computation ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ On the power of parity polynomial time ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ On sparse hard sets for counting classes ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Lower bounds and the hardness of counting properties ⋮ Reductions to sets of low information content ⋮ Probabilistic polynomial time is closed under parity reductions ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ SELF-SPECIFYING MACHINES ⋮ Tally NP sets and easy census functions. ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ Kolmogorov characterizations of complexity classes ⋮ Gap-definable counting classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On the construction of parallel computers from various basis of Boolean functions
• On one-way functions and polynomial-time isomorphisms
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Complexity classes without machines: on complete languages for UP
• Collapsing degrees
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• Enumerative counting is hard
• One-way functions and the nonisomorphism of NP-complete sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• On the unique satisfiability problem
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• The difference and truth-table hierarchies for NP
• Complexity Measures for Public-Key Cryptosystems
• Nondeterministic Space is Closed under Complementation
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Complexity of Enumeration and Reliability Problems
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On the Accepting Density Hierarchy in NP
• Near-Testable Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-Printable Sets
• On the power of parity polynomial time
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: On the power of parity polynomial time