We extend Nisans breakthrough derandomization result that BP_HL subseteq SC^2 [11] 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 BP_HLOGCFL) can be simulated by an SC^2 machine. This derandomization result improves a classical result by Cook [7] that LOGDCFL sybseteq SC^2 since LOGDCFL is contained in BP_HLOGCFL. We also present a simple circuit-based proof that BP_HLOGCFL is in NC^2.
展开▼
