Derandomization of Probabilistic Auxiliary Pushdown Automata Classes
H. Venkateswaran · 2006
We extend Nisan's breakthrough derandomization result that BPHL sube SC2(1992) to bounded error probabilistic complexity classes based on auxiliary pushdown automata. In particular, we show that any logarithmic space, polynomial time two-sided bounded-error probabilistic auxiliary pushdown automaton (the corresponding complexity class is denoted by BPHLOGCFL) can be simulated by an SC2machine. This derandomization result improves a classical result by Cook (1979) that LOGDCFL sube SC2since LOGDCFL is contained in BPHLOGCFL. We also present a simple circuit-based proof that BPHLOGCFL is in NC2