О сложности вычисления рудиментарных предикатов

Класс рудиментарных предикатов определяется как наименьший класс числовых предикатов, который содержит предикаты равенства и конкатенации и замкнут относительно операций логики высказываний, явных преобразований и навешивания ограниченных кванторов. Сложность вычисления рудиментарных предикатов охарактеризовывается в терминах альтернирующих машин Тьюринга с конечным числом альтернирований. Доказывается полиномиальная вычислимость рудиментарных $\exists$- и $\forall$-предикатов на детерминированных машинах Тьюринга. Определяются иерархии $\{R\Sigma_k\}$ и $\{R\Pi_k\}$ класса рудиментарных предикатов и исследуется класс $R\Sigma_1\cap R\Pi_1$. Доказывается неразрешимость проблемы непустоты для класса $R\Pi_1$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 00–01–00351.