March 6th, 2011

nyaload

P ?= NP

Вот есть страшилка, что докажут что P == NP и тогда сломается шифрование, смогут найти доказательства любых теорем, и ещё много в мире изменится. Или что докажут P != NP, и тогда можно вздохнуть с облегчением, что в мире есть надёжные вещи и непостижимые загадки.

P и NP - это не тот вопрос, который важен для мира. Важнее - "есть ли эффективный алгоритм, решающий NP-полные задачи." Полиномиальный - ещё не значит "эффективный".

Если найдут алгоритм решения SAT/коммивояжёра работающий за полиномиальное O(n^(10^100)) время, вряд ли что-то изменится. Хоть он и полиномиальный и P == NP.

Если найдут алгоритм решающий NP-полные задачи за O(N^log(log(N))) и быстрее нельзя, изменится очень много, хотя это будет доказательством P != NP. Хотя N^log(log(N)) растёт быстрее любого полинома.

ЗЫ. Задача об упаковке рюкзака (запихать в ограниченную грузоподъёмность максимум веса из данного списка предметов) - полиномиальна от размера рюкзака. Хотя и неполиномиальна от количества битов чисел, которые представляют размер рюкзака и предметов. А значит на практике - вполне решаема, для размеров рюкзака 1000, 100000 и тп, а для больших рюкзаков - можно мерять их размер в литрах, а не миллилитрах (если предметы не слишком мелкие)

Достаточно завести табличку или множество длины N, какие веса можно скомбинировать из предметов. А при добавлении нового предмета веса m - обновить табличку, добавив в ней для каждого элемена x ещё и (x+m), в начале в табличке только 0. Если у нас M предметов, то получится 2^M сумм, но у этих 2^M сумм будет не больше N несовпадающих ячеек в таблице.