On the Structure of Logspace Probabilistic Complexity Classes

DOI10.1137/S0097539796298339MaRDI QIDQ4943854zbMATH OpenOpenAlexFDO

Authors 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) Discrete mathematics in relation to computer science (68R99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parallel algorithms in computer science (68W10)

Recommendations

• On the structure of log-space probabilistic complexity classes (extended abstract)
• Probabilistic complexity classes and lowness
• scientific article; zbMATH DE number 4062587
• On relationships between approximate and probabilistic complexity classes
• On relativized exponential and probabilistic complexity classes
• Generalized lowness and highness and probabilistic complexity classes
• Space-bounded hierarchies and probabilistic computations
• On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering
• The Probabilistic Theory of Linear Complexity
• The structure of logarithmic advice complexity classes

Cited in

(9)

• On the structure of log-space probabilistic complexity classes (extended abstract)
• On a complexity hierarchy between L and NL
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• The structure of logarithmic advice complexity classes
• Space-bounded hierarchies and probabilistic computations
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Multihead two-way probabilistic finite automata (extended abstract)
• scientific article; zbMATH DE number 951900 (Why is no real title available?)
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines

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

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