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

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