В. Николаенко

Существование полных множеств

В докладе будет рассмотрено определение класса языков Sparse. Будет доказан факт, о том, что
существование оптимальной системы доказательств для тавтологий влечет существование полного языка в классе
$NP \cap Sparce$. Также в докладе будут рассмотрены promise классы и будет доказан следующий факт:
если существует оптимальная система доказательств для TAUT, то существует полное множемтво для promise
классов ($NP \cap co-NP, ZPP, BPP, RP, ...$)