scientific article; zbMATH DE number 8788

zbMATH Open0744.68052MaRDI QIDQ3971277FDOQ3971277

Authors: Eric Allender, K. W. Wagner 

Publication date: 25 June 1992

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

counting hierarchyThreshold circuits

Mathematics Subject Classification ID

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

Cited In (8)

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

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)