Нижние оценки для полиномиального исчисления в случае идеалов, отличных от биномиальных

Обобщаются недавние линейные нижние оценки на степень вывода в полиномиальном исчислении, основанные на рассмотрении биномиальных идеалов. Мы предлагаем достаточно общий критерий трудности булевых функций (называемый нами иммунностью), которому, в частности, удовлетворяет случайная булева функция, и доказываем нижние оценки на степень вывода для широкого класса тавтологий, основанных на иммунных функциях. В качестве одного из приложений наших методов мы обобщаем цейтиновские тавтологии по модулю $p$ на случай булевых переменных (т.е. в присутствии аксиом $x_i^2=x_i$) и доказываем трудность их вывода в полиномиальном исчислении над любым полем характеристики, отличной от $p$. Затем по аналогии с цейтиновскими мы определяем “потоковые” тавтологии, основанные на функции голосования, и показываем их трудность над любым полем. Также мы доказываем нижнюю оценку $\Omega(n)$ на степень вывода случайных $k$-КНФ в полиномиальном исчислении над полями характеристики 2.