?

Log in

No account? Create an account
P = NP - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

P = NP [21 January 2011|17:31]
Oleg Eterevsky

Пост для математиков и примкнувшим к ним.

В свете недавнего «доказательства» на Хабре того, что P = NP, я тут задался следующим вопросом: а ведь если бы и вправду придумали полиномиальный алгоритм для NP-задач, что бы это означало для математики? Задача поиска доказательства для любой данной теоремы относится к классу NP, ведь коль скоро доказательство приведено (и написано на формальном языке), его проверка вполне возможна за полиномиальное время. Конечно, полином это от длины доказательства, а не от длины утверждения, но всё равно неплохо.

Мораль: если кто-то придумает алгоритм, решающий NP-полную задачу, он сможет претендовать не только на 1000000$ причитающиеся за эту задачу от института Клэя, но и ещё на 5 таких же призов за оставшиеся 5 нерешённых задач. Выгода.

LinkReply

Comments:
From: viktorpetrov
2011-01-21 03:01 pm (UTC)
Ну допустим даже есть алгоритм, находящий доказательство длины N за O(N^2). Теперь оцени размер, скажем, доказательства Уайлса, записанного в виде, пригодном для проверки компьютером, и возведи в квадрат.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 04:02 pm (UTC)
Кстати сказать, объём формальных доказательств не так чтобы слишком велик, так что всё реалистично. Можно и поднапрячься с вычислительными ресурсами. :)
(Reply) (Parent) (Thread)
[User Picture]From: cavaler
2011-01-21 03:12 pm (UTC)
Я так понимаю, что это главным образом будет иметь теоретические последствия. Например, в виде теоретического краха почти всей современной криптографии, там же куча всего завязана на NP.

Практические - далеко не так сильно и не сразу. Полином полиномом - но коэффициенты в нем могут быть до небес.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 04:04 pm (UTC)
Ну дык возможность автоматически доказать или опровергнуть любую теорему — нехилые такие теоретические последствия.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: edwardahirsch
2011-01-21 04:57 pm (UTC)
А главное, они будут неожиданно падать на голову!

(Свиньи, которые будут летать :) )

Что полином таки от длины доказательства, это тоже "печально". Которое может иметь потенциально совершенно какую угодно длину. Причём в слегка другой системе доказательств оно будет иметь совершенно другую длину.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:21 pm (UTC)
То есть простор для творчества у математиков всё-таки будет: выдумывать более оптимальные системы доказательств.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: mihaild
2011-01-21 05:13 pm (UTC)
Полиномы бывают очень разные. Даже сотая степень от длины доказательства - это уже очень печально. А может быть и во много раз больше.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:18 pm (UTC)
Нет, ну положа руку на сердце, много ли мы знаем алгоритмов медленнее n^4?
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-21 05:25 pm (UTC)
Ну например AKS - работает за n^6.
Кроме того, алгоритмов, решающих NP-полную задачу за полиномиальное время мы знаем меньше.
И, кроме того, есть задача, которую нельзя сделать за n^4, но можно за n^9 (например).
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: dmitrits
2011-01-21 05:27 pm (UTC)
Найти доказательство одного доказуемого утверждения можно за константное время: перебирать все строчки и проверять, являются ли они доказательствами. Если даже для SAT будет алгоритм, работающий Cn^2, где C=2^300, то о практике речь уже идти не будет.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 05:42 pm (UTC)
Я ж не говорю о поиске доказательства конкретной теоремы. Я говорю об общем алгоритме.
(Reply) (Parent) (Thread) (Expand)
From: ajtkulov
2011-01-21 07:03 pm (UTC)
А точно ли, что все остальные задачи (со стоимостью 10^6) лежат в NP?
Такое ощущение, что все интересное начинается с NEXPTIME и выше, а там все плохо даже если окажется равенство между P и NP...
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-21 07:23 pm (UTC)
Это ж не алгоритмические задачи, а математические. Какой тут NEXP?
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: ted_dy
2011-01-21 08:25 pm (UTC)
Что-то я не понял... это всё при условии, что решение есть...
(Reply) (Thread)
[User Picture]From: mihaild
2011-01-21 09:33 pm (UTC)
Это при условии, что не только решение существует, но и кто-то его найдет.
(Reply) (Parent) (Thread) (Expand)