A note on the advice complexity of multipass randomized logspace

DOI10.4230/LIPICS.MFCS.2016.31MaRDI QIDQ4608590zbMATH OpenOpenAlexFDO

Authors Peter B. Dixon, Debasis Mandal, Aduri Pavan, N. V. Vinodchandran

Publication date 21 March 2018

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6500/pdf/LIPIcs-MFCS-2016-31.pdf/

zbMATH Keywords

advicerandomized machinesspace-bounded computations

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On probabilistic space-bounded machines with multiple access to random tape
• Linear Advice for Randomized Logarithmic Space
• On read-once vs. multiple access to randomness in logspace
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Space hierarchy results for randomized models

Cited in

(4)

• On read-once vs. multiple access to randomness in logspace
• The structure of logarithmic advice complexity classes
• On probabilistic space-bounded machines with multiple access to random tape
• Linear Advice for Randomized Logarithmic Space

This page was built for publication: A note on the advice complexity of multipass randomized logspace

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