О нижних оценках времени вычислений

Вводится специальное представление предикатов с помощью полных систем признаков. Для определенного класса предикатов установлена связь их представлений с временем вычисления на машинах Тьюринга. Таким путем описан класс предикатов с квадратичной нижней оценкой временной сложности. Сформулирована гипотеза, утверждающая наличие подобной связи для существенно более широкого класса представлений. Принятие этой гипотезы дает для соответствующих предикатов экспоненциальную нижнюю оценку временной сложности.