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

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

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

• 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?)
• 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
• 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)