On log-time alternating Turing machines of alternation depth k

DOI10.1007/bfb0030843zbMath1527.68062MaRDI QIDQ6085715

Jian'er Chen, Li-Ming Cai

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

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)

Cites Work

• Unnamed Item
• On input read-modes of alternating Turing machines
• On finding a minimum dominating set in a tournament
• On uniform circuit complexity
• Characterizing parallel hierarchies by reducibilities
• Optimization, approximation, and complexity classes
• Nondeterministics circuits, space complexity and quasigroups
• Classes of bounded nondeterminism
• A taxonomy of problems with fast parallel algorithms
• Alternation
• An Optimal Parallel Algorithm for Formula Evaluation
• Nondeterminism within $P^ * $

This page was built for publication: On log-time alternating Turing machines of alternation depth k