О сложности монотонных вычислений многочленов

Доказана теорема, обобщающая некоторые результаты О. М. Касим-заде и К. П. Шнорра. С ее помощью построены примеры многочленов с высокой монотонной сложностью, в частности пример многочлена $f$ с монотонной сложностью $O(2^{2/3\operatorname{degf}})$. Выдвинута комбинаторная гипотеза, из справедливости которой вытекает возможность построения еще более сложных многочленов.
Библиогр. 14.