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

Класс рудиментарных предикатов определяется как наименьший класс числовых предикатов, который содержит предикаты равенства и конкатенации и замкнут относительно операций логики высказываний, явных преобразований и навешивания ограниченных кванторов. Рассматриваются два класса рудиментарных предикатов. Первый класс состоит из предикатов, которые имеют в предваренной нормальной форме специального вида кванторную приставку типа $\exists\forall$. У предикатов второго класса кванторная приставка может быть произвольной, но ограничения налагаются на скулемовские разрешающие функции. Доказывается, что любой предикат каждого из этих классов можно вычислить подходящим детерминированным алгоритмом за полиномиальное время.
Библиография: 8 названий.