Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 9 декабря, комната 106. Начало в 17:30.

Докладчик: С. Федин.

Тема: Гипотезы, приводящие к субэкспоненциальным алгоритмам для выполнимости.

Abstract

Доклад по манускрипту Райана Вильямса.

Будут приведены три гипотезы, и доказано, что справедливость каждой из них влечет существование работающего порядка $2^{d n}$ полиномиальных по времени шагов алгоритма для CNF-SAT (где $d < 1$). Гипотезы эти касаются, в частности, времени работы алгоритмов для простых (разрешимых за полиномиальное время) задач.