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

Задачи регулярной реализуемости – это задачи проверки непустоты пересечения некоторого заданного языка (фильтра) с регулярным языком. Ниже рассматривается вопрос о выразительной силе этого класса задач. Доказано, что для любого языка существует задача регулярной реализуемости, эквивалентная этому языку относительно дизъюнктных сводимостей на недетерминированной логарифмической памяти. Как следствие, доказано существование полных относительно полиномиальной сводимости задач регулярной реализуемости для всех уровней полиномиальной иерархии.