Home

Семинар 5 декабря 2003 года

Пятница, 5 декабря, комната 106. Начало в 19:00.

Докладчик: Д. Ицыксон.

Тема: Короткие доказательства невыполнимости случайных формул.

Abstract

Доклад по статье Joel Friedman, Andreas Goerdt, Michail Krilevich "Recognizing more unsatisfable random k-SAT instances efficiently".

В докладе будут рассматриваться случайные формулы в k-КНФ. Если число клозов m достаточно велико по сравнению с числом переменных n, то с большой вероятностью случайная формула будет невыполнимой. Для m начиная с $ n^(k/2) $ (для чётных k) будет приведён полиномиальный алгоритм, который с большой вероятностью докажет, что случайно выбранная формула невыполнима. По ходу дела, будет доказан и использован забавный факт о связи собственных чисел матриц и размера максимального независимого множества графа: максимальное собственнное число матрицы псевдосмежности неориентированного графа (1 - если есть ребро, q - если нет ребра) не меньше размера максимального независимого множества его вершин.