Laboratory of Mathematical Logic at PDMI

Пятница, 19 октября, комната 106. Начало в 17:45.

Докладчик: А. Кожевников.

Тема: О невозможности сжатия SAT.

Abstract

Язык L из NP называется сжимаемым, если существуют такие язык A и полиномиально вычислимое сведение f языка L к языку А, что для любого слова x из L длина f(x) полиномиально ограничена относительно размера доказательства x в L.

Доклад посвящен недавнему результату L.Fortnow and R.Santhanam о том, что из что сжимаемости SAT следует то, что coNP содержится в NP/poly, и разнообразным следствиям этого факта.