$S_{k,\exp}$ does not prove $\mathrm{NP}=\mathrm{co}-\mathrm{NP}$ uniformly

Вводится понятие равномерного доказательства в исчислении секвенций. Затем показывается, что в $S_{k,\exp}$ (условии хорошо изученной системы $S_k$, ограниченной арифметики Басса) не существует равномерного доказательства $\mathrm{NP}=\mathrm{co}=\mathrm{NP}$. Получен также немного более сильный результат: в $S_{k,\exp}$ не существует равномерного доказательства $\widehat\Sigma^b_{1,k'}=\widehat\Pi_{1,k'}^b$ для $2\le k'\le k$. Затем, применяя вариант того же метода, показывается, что $S_{k,\exp}$ не доказывает теорему Дэвиса–Патнама–Робинсона–Матиясевича. В этом результате условие равномерности не упоминается. Затем представлено обобщение обоих результатов на более высокие уровни иерархии Гжегорчика. Библ. – 21 назв.