Relations among parallel and sequential computation models

DOI10.1007/BFB0027776MaRDI QIDQ6560351zbMATH OpenFDO

Authors Heribert Vollmer

Publication date 21 June 2024

Full work available at URL https://doi.org/10.1007/BFB0027776

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Networks and circuits as models of computation; circuit complexity (68Q06) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On similarity and duality of computation (I)
• Relativized circuit complexity
• Parallel models of computation: An introductory survey
• Parallelism in random access machines
• scientific article; zbMATH DE number 4068238

Cites work

• A uniform approach to define complexity classes
• Alternation
• Complete sets and the polynomial-time hierarchy
• Complexity classes defined by counting quantifiers
• Counting classes: Thresholds, parity, mods, and fewness
• Depth reduction for circuits of unbounded fan-in
• scientific article; zbMATH DE number 8788 (Why is no real title available?)
• scientific article; zbMATH DE number 1346528 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• On balanced versus unbalanced computation trees
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Parity, circuits, and the polynomial-time hierarchy
• Some observations on the connection between counting and recursion
• Tally languages and complexity classes

This page was built for publication: Relations among parallel and sequential computation models

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