On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages

摘要

We study the circuit complexity of generating at random a word of length n from a given language under uniform distribution. We prove that, for every language accepted in polynomial time by 1-NAuxPDA of polynomially bounded ambiguity, the problem is solvable by a logspace-uniform family of probabilistic boolean circuits of polynomial size and O(log{sup}2 n) depth. Using a suitable notion of reducibility (similar to the NC{sup}1-reducibility), we also show the relationship between random generation problems for regular and context-free languages and classical computational complexity classes such as DIV, L and DET.