scientific article; zbMATH DE number 4041255

MaRDI QIDQ3779736zbMATH OpenFDO

Authors Thomas Gundermann, Gerd Wechsung

Publication date 1987

zbMATH Keywords

counting classnondeterministic Turing machinesrelativizations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1953880
• scientific article; zbMATH DE number 1414307
• Classes of bounded counting type and their inclusion relations
• Counting partial types in simple theories
• A Finite First-Order Theory of Classes
• Classification in finite model theory: counting finite algebras
• scientific article; zbMATH DE number 3987268
• Finite type invariants
• Implicit recursion-theoretic characterizations of counting classes
• scientific article; zbMATH DE number 5066581

Cited in

(22)

• The chain method to separate counting classes
• A second step towards complexity-theoretic analogs of Rice's Theorem
• A reducibility for the dot-depth hierarchy
• Exact computation of the number of accepting paths of an NTM
• Relativized counting classes: Relations among thresholds, parity, and mods
• Hierarchies and reducibilities on regular languages related to modulo counting
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• scientific article; zbMATH DE number 1222829 (Why is no real title available?)
• Complexity classes defined by counting quantifiers
• scientific article; zbMATH DE number 1953880 (Why is no real title available?)
• scientific article; zbMATH DE number 1507219 (Why is no real title available?)
• Classes of bounded counting type and their inclusion relations
• scientific article; zbMATH DE number 1418356 (Why is no real title available?)
• scientific article; zbMATH DE number 1414307 (Why is no real title available?)
• On the power of parity polynomial time
• Locally definable acceptance types for polynomial time machines
• On the power of parity polynomial time
• On the acceptance power of regular languages
• On the limiting proportion of types
• Probabilistic polynomial time is closed under parity reductions
• On the complexity of counting in the polynomial hierarchy

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 Q3779736)