scientific article; zbMATH DE number 8788

MaRDI QIDQ3971277zbMATH OpenFDO

Authors Eric Allender, K. W. Wagner

Publication date 25 June 1992

zbMATH Keywords

counting hierarchyThreshold circuits

Mathematics Subject Classification ID

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

Recommendations

• A simple proof of Toda's theorem
• PP is as Hard as the Polynomial-Time Hierarchy
• A circuit-based proof of Toda's theorem
• Complexity classes defined by counting quantifiers

Cited in

(7)

• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• Same-decision probability: a confidence measure for threshold-based decisions
• Simple characterizations of \(P(\# P)\) and complete problems
• On closure properties of bounded two-sided error complexity classes
• Counting problems for Parikh images
• A simple proof of Toda's theorem
• Relations among parallel and sequential computation models

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3971277)