Home

Семинар 9 декабря 2005 года

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

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

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

Abstract

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

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