On input read-modes of alternating Turing machines

DOI10.1016/0304-3975(94)00253-FzbMath0873.68055MaRDI QIDQ672377

Li-Ming Cai, Jian'er Chen

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Related Items

On fixed-parameter tractability and approximability of NP optimization problems, Gap-languages and log-time complexity classes, On log-time alternating Turing machines of alternation depth k

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On uniform circuit complexity
• Characterizing parallel hierarchies by reducibilities
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Logical definability of NP optimization problems
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• A taxonomy of problems with fast parallel algorithms
• Alternation
• An Optimal Parallel Algorithm for Formula Evaluation