On the Structure of Logspace Probabilistic Complexity Classes

DOI10.1137/S0097539796298339zbMath0941.68051OpenAlexW2087824917MaRDI QIDQ4943854

Ioan I. Macarie

Publication date: 19 March 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796298339

zbMATH Keywords

probabilistic Turing machinesprobabilistic computationgames against natureArthur-Merlin gamesmultihead finite automatalogspace reductionsheads hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)

This page was built for publication: On the Structure of Logspace Probabilistic Complexity Classes