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

Article

О выразительной силе задач регулярной реализуемости

Проблемы передачи информации. 2013. Т. 49. № 3. С. 86-104.
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. We conclude from this result an existence of complete problems under polynomial reductions for many complexity classes including all classes of the polynomial hierarchy.