On the power of parity polynomial time
From MaRDI portal
Publication:5096157
DOI10.1007/BFb0028987zbMath1492.68054MaRDI QIDQ5096157
Hemaspaandra, Lane A., Jin-Yi Cai
Publication date: 16 August 2022
Published in: STACS 89 (Search for Journal in Brave)
Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Non-deterministic communication complexity with few witnesses ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Turing machines with few accepting computations and low sets for PP ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ On the power of enumerative counting ⋮ A uniform approach to define complexity classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- BPP and the polynomial hierarchy
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Complexity classes without machines: on complete languages for UP
- Graph isomorphism is in the low 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
- 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
- Complexity Measures for Public-Key Cryptosystems
- The Boolean Hierarchy II: Applications
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
This page was built for publication: On the power of parity polynomial time
