Probabilistic polynomial time is closed under parity reductions

DOI10.1016/0020-0190(91)90140-DzbMath0714.68031MaRDI QIDQ751270

Gerd Wechsung, Richard Beigel, Hemaspaandra, Lane A.

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityprobabilistic polynomial time

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

A complexity theory for feasible closure properties ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Manipulating the quota in weighted voting games ⋮ On sparse hard sets for counting classes ⋮ Graph isomorphism is low for PP ⋮ A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy ⋮ Circuits over PP and PL ⋮ Kolmogorov characterizations of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• The complexity of facets (and some facets of complexity)
• The complexity of combinatorial problems with succinct input representation
• The complexity of optimization problems
• Bounded queries to SAT and the Boolean hierarchy
• The difference and truth-table hierarchies for NP
• Computational Complexity of Probabilistic Turing Machines
• On the power of parity polynomial time

This page was built for publication: Probabilistic polynomial time is closed under parity reductions