• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Universality of regular realizability problems

Lecture Notes in Computer Science. 2013. Vol. 7913. P. 271-282.

A regular realizability (RR) problem is to test nonemptiness of the intersection of some fixed language (filter) with a given 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 on nondeterministic log space.

We deduce from this result the existence of RR problems complete under polynomial reductions for many complexity classes including all classes of the polynomial hierarchy.