Ого!

[plakhov]

(извините все, кому будет непонятно)

There is a deterministic algorithm for B2-formula-SAT which runs in time 2(1-μc)n on formulas of size at most cn. Here μc > 0 is a constant only depending on cЧто-то я полностью пропустил эту ветвь исследований (в статье ещё довольно много ссылок на аналогичные результаты), а ведь это же не шутка: грубо говоря

Comments

[ext_830324]

Ого!

[109]

> например, с=10), после чего решать NP-полные задачи размером сN за то же время перебора, за которое мы раньше решали NP-полные задачи размером N

наверное, ты хотел сказать размером N/c? а то получается, что задача стала больше :)

и ещё. либо не все NP-полные задачи можно трансформировать таким образом, либо процедуру можно применять рекурсивно. либо я чего-то не понимаю.

[cunctator_]

бОльшая задача за то же время.

[109]

я не уверен, что понимаю вас. у нас есть задача фиксированного размера. её надо решить быстрее. метод по ссылке поможет, или нет? (очевидно, факт того, что какую-то другую задачу можно решить за то же время не помогает нам решить *нашу* задачу быстрее)

[visualdoj]

Наша цель - решить задачу для cN. Мы делаем препроцессинг и в итоге получаем возможность решить её за то же время, за которое решается задача для N, т.е. заметно быстрее.

[major_m]

> почему это не алгоритм Жизни, Вселенной и всего такого?

Есть некоторые проблемы.
1. Алоритм работает только на {AND, OR, XOR}-формулах (на B2 можно забить). Сведение произвольной NP задачи к такой формуле может увеличить число переменных, например, в полином раз.
2. \mu_c = 2^{ - \Theta(n^3)}. По мере увеличения формулы относительно числа переменных, верхняя граница будет все хуже и хуже.
3. Да, формулу размера cn всегда можно решить за O*(2^n). Размер --- это длина строки, а не число переменных.

[plakhov]

Да, я неправильно понял утверждение: мне показалось, что n - не число переменных x_i, а просто произвольное число. Жаль. :)

[sim0nsays]

Тут Петя на Кружочках рассказывает свое понимание (там прилично текста, поэтому я только линк):

https://dl.dropbox.com/u/2853848/bm25/np.txt

Не выглядит тотальным и абсолютным счастьем, но может я что не так понял.

[plakhov]

Ага, спасибо, я уже с утра почитал доказательство, и осознал, что утверждение понял неправильно. n в теореме не свободный параметр, а кол-во переменных в формуле. Тогда действительно не очень интересно, конечно.

[mitrichu]

Гляньте, но по всему тэту: примерно на эту же тему:

http://mitrichu.livejournal.com/tag/Математика