On expressive power of regular realizability problems
M. Vyalyi · Problems of Information Transmission · 2013
A regular realizability (RR) problem is a problem of testing nonemptiness of intersection of some fixed language (filter) with a regular language. We show that RR problems are universal in the following sense. For any language L there exists an RR problem equivalent to L under disjunctive reductions in nondeterministic log space. From this result, we derive existence of complete problems under polynomial reductions for many complexity classes, including all classes of the polynomial hierarchy.