С. Капулкин (АФТУ) p-оптимальные системы доказательств
По статье ''Optimal acceptors and optimal proof systems'', автор Э.А.Гирш. Доклад является введением в проблематику систем доказательств и аксепторов. Поиск системы доказательств для языка тавтологий с доказательствами полиномиальной длины связан с вопросом $\mathbf{NP}$ vs $\mathbf{co{-}NP}$. Акспеторами называются машины, останавливающиеся на входах из языка и только на них. В докладе показывается связь между существованием p-оптимальных систем доказательств и оптимальных аксепторов. Доказывается существование p-оптимальных систем доказательств с одним битом подсказки.
