Институт Клея и теорема P=NP

[Vieux]

Здравствуйте друзья!
Пусть некоторый автор нашел отличное доказательство того, что P=NP (например, O($n^2$)).
По требованиям института Клея, данный автор должен опубликовать доказательство в какой-нибудь математический журнал с хорошей репутацией. Отсюда у меня возникают следующие вопросы и опасения:
1- не будет ли украдено доказательство?
2- если все-таки доказательство выйдет на свет, не произойдет ли финансовый или даже политический кризис, так как всякие хакеры и крекеры получат реальные возможности взламывать банки, цифровые подписи, гос. тайны и т.п.
3- мне кажется, что к некоторым задачам из списка задач тысячелетия требования по публикации должны быть немного другие. Или для института Клея очевидно, что $P\not=NP$?
4-Вообще как Вы думаете, человеку который нашел такое доказательство стоит сразу опубликовать его или есть более разумный (не рискованный) способ заявить об этом?
Спасибо.

[Urnwestek]

Цитата:

1- не будет ли украдено доказательство?

Если сильно боитесь, то можете запатентовать. Патент, вроде, дают на что угодно.

Цитата:

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

Разные люди на этот вопрос отвечают по-разному. Моё мнение — нет, есть множество криптосистем, которые не завязаны на NP-полноте какой-либо задачи и множество задач, для которых их принадлежность к NP неопределена (задача факторизации, например). Но, действительно, многие задачи логистики, искусственного интеллекта и автоматических доказательств станет решать в разы легче.

Цитата:

мне кажется, что к некоторым задачам из списка задач тысячелетия требования по публикации должны быть немного другие. Или для института Клея очевидно, что $P\not=NP$?

Не вижу как из первого следует второе. Чем вам не нравятся текущие требования?

Цитата:

4-Вообще как Вы думаете, человеку который нашел такое доказательство стоит сразу опубликовать его или есть более разумный (не рискованный) способ заявить об этом?

Это на усмотрение человека. Я бы не публиковал, честно говоря.

Не сочтите за дерзость, но если этот самый человек, это вы, то я сильно сомневаюсь, что вы нашли доказательство. И не потому, что его не нашёл никто до вас, а потому, что

Цитата:

P=NP (например, O($n^2$)).

высказывание либо малоосмысленное, либо очевидно неверное (известны задачи из класса P, для которых доказана оценка $\Omega(n^3)$).

[Vieux]

Цитата:

Если сильно боитесь, то можете запатентовать. Патент, вроде, дают на что угодно.

Математические доказательства, алгоритмы не патентуются.

Цитата:

есть множество криптосистем, которые не завязаны на NP-полноте какой-либо задачи и множество задач, для которых их принадлежность к NP неопределена (задача факторизации, например).

RSA алгоритм связан с факторизацией, а она легко сведется к задаче SAT.

Цитата:

Не вижу как из первого следует второе. Чем вам не нравятся текущие требования?

Требование о публикации в открытом доступе, в случае P равно NP (например, найден алгоритм O($n^2$) для задачи SAT) считаю не дальновидным, так как мягко говоря имеет неприятные последствия.

Цитата:

Не сочтите за дерзость, но если этот самый человек, это вы, то я сильно сомневаюсь, что вы нашли доказательство. И не потому, что его не нашёл никто до вас, а потому, что

Цитата:

P=NP (например, O($n^2$)).

высказывание либо малоосмысленное, либо очевидно неверное (известны задачи из класса P, для которых доказана оценка $\Omega(n^3)$).

Во-первых не говорил, что я что-то доказал. Во-вторых Вы имеете право на сомнение.В-третьих, видимо Вы просто не поняли о чем речь. Я имел ввиду O($n^2$) для задачи SAT.

[Urnwestek]

Цитата:

Математические доказательства, алгоритмы не патентуются.

Так вы и запатентуете математическое доказательство. Контрпример — тоже математическое доказательство.

Цитата:

RSA алгоритм связан с факторизацией, а она легко сведется к задаче SAT.

Действительно сводится, снова я всё перепутал, извиняюсь.

Цитата:

Требование о публикации в открытом доступе, в случае P равно NP (например, найден алгоритм O($n^2$) для задачи SAT) считаю не дальновидным, так как мягко говоря имеет неприятные последствия.

Как я уже говорил, по мне так к катастрофе это не приведёт. Перейдут с RSA на какие-нибудь эллиптические штуки, делов-то. Да и альтернативы особой нету, было бы неприятно, если бы приз выдался кому-то, чей контрпример видело 10-20 человек максимум.

Цитата:

Во-первых не говорил, что я что-то доказал. Во-вторых Вы имеете право на сомнение.В-третьих, видимо Вы просто не поняли о чем речь. Я имел ввиду O($n^2$) для задачи SAT.

Всё я правильно понял, любую задачу из класса $NP$ можно свести к 3-SAT. И если 3-SAT будет работать за $O(n^2)$ это будет означать, что задач выполняемых за $\omega(n^2)$ в классе $P$ нету. Так как они есть, получаем противоречие.

[Portnov]

Мне кажется, большой практической проблемы решение вопроса P=NP не создаст, скорее всего. Исходя из того, сколько над этим вопросом уже думают, мне кажется, что в итоге почти наверняка будет одно из трёх решений:
а) выяснится, что это «гёделевское утверждение» (его можно сформулировать, но нельзя ни доказать, ни опровергнуть). Практического выхлопа (для криптографии итд) от такого «решения» не будет вообще никакого. «Стало известно, что ничего не известно».
б) выяснится, что это утверждение «зависит» от одного из известных «гёделевских утверждений». Например, «если принять аксиому выбора, то P=NP». Практического выхлопа, опять же, ноль.
в) самый «оптимистичный» вариант: удастся построить доказательство P=NP, но оно будет неконструктивным, т.е. не будет включать способ получения P-алгоритма из любого NP. Практический выхлоп либо нулевой, либо появится только на очень сложных случаях. Так, для каких-то задач, про которые раньше не было известно P оно или NP, в последние десятилетия удалось построить P-алгоритмы, но на практике эти алгоритмы почти не применяются (http://ru.wikipedia.org/wiki/Тест_Агравала_—_Каяла_—_Саксены в качестве примера).

[Urnwestek]

Я, может, чего-то очень сильно не понимаю в логике, но

Цитата:

б) выяснится, что это утверждение «зависит» от одного из известных «гёделевских утверждений». Например, «если принять аксиому выбора, то P=NP». Практического выхлопа, опять же, ноль.

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

[Yuri Gendelman]

Vieux в сообщении #773055 писал(а):

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

Хачиян разработал полиномиально сложный (P) метод решения задачи линейного программрования. Но на практике по-прежнему пользуются экспоненциально сложным (NP) симплексным методом.

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

Между прочим, чтобы найти корень нелинейного уравнения на интервале [0.0; 1.0] с точностью до 0.1 самый эффективный - метод полного перебора.

[Vieux]

Yuri Gendelman в сообщении #773147 писал(а):

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

эффективно реализуемый алгоритм и есть O($n^2$) или O($n^3$) для задачи SAT.

[Xaositect]

Vieux в сообщении #773055 писал(а):

2- если все-таки доказательство выйдет на свет, не произойдет ли финансовый или даже политический кризис, так как всякие хакеры и крекеры получат реальные возможности взламывать банки, цифровые подписи, гос. тайны и т.п.
3- мне кажется, что к некоторым задачам из списка задач тысячелетия требования по публикации должны быть немного другие. Или для института Клея очевидно, что $P\not=NP$?

Я думаю, вряд ли кто-нибудь всерьез принимает возможность того, что даже если $\mathbf{P} = \mathbf{NP}$, первый полученный полиномиальный алгоритм будет практически эффективным.

Vieux в сообщении #773084 писал(а):

RSA алгоритм связан с факторизацией, а она легко сведется к задаче SAT.

Это верно, но в определении сводимости алгоритм сведения должен быть полиномиальным, и конкретно для сведения факторизации к SAT алгоритм сведения преобразует схему для умножения двоичных чисел в формулу и размер итоговой формулы для SAT пропорционален размеру схемы, то есть мы уже получаем не $n^2$, а $(Cn\log n\log \log n)^2$

Urnwestek в сообщении #773105 писал(а):

Как я уже говорил, по мне так к катастрофе это не приведёт. Перейдут с RSA на какие-нибудь эллиптические штуки, делов-то.

Эллиптические штуки (конкретно, задача elliptic curve discrete logarithm) также лежат в NP. Правда, там уже сводимость к SAT по всей видимости будет сложнее.

Portnov в сообщении #773119 писал(а):

а) выяснится, что это «гёделевское утверждение» (его можно сформулировать, но нельзя ни доказать, ни опровергнуть). Практического выхлопа (для криптографии итд) от такого «решения» не будет вообще никакого. «Стало известно, что ничего не известно».
б) выяснится, что это утверждение «зависит» от одного из известных «гёделевских утверждений». Например, «если принять аксиому выбора, то P=NP». Практического выхлопа, опять же, ноль.

На самом деле, эти два случая могут означать, что полиномиальный алгоритм на самом деле (т.е. в стандартной модели) существует, но доказать его полиномиальность и/или корректность нельзя. Чисто теоретически такой алгоритм можно даже найти. Практически это действительно вряд ли значимо.

Vieux в сообщении #773155 писал(а):

эффективно реализуемый алгоритм и есть O($n^2$) или O($n^3$) для задачи SAT.

Вы забываете про константы. Для эффективной работы это должно быть не просто $O(n^2)$, а $O(n^2)$ с небольшой константой. Например, есть лазерный метод Штрассена для умножения матриц за $O(n^{2.48})$ (есть еще алгоритм Копперсмита-Винограда и его вариация Василевской-Вильямс, но там свои заморочки: сам алгоритм напрямую не строится, доказывается его существование верояностным методом), но на практике все равно пользуются первым быстрым алгоритмом Штрассена со сложностью $O(n^{2.81})$, ибо он становится медленнее только на астрономического размера матрицах.

-- Чт окт 10, 2013 00:53:37 --

Yuri Gendelman в сообщении #773147 писал(а):

Хачиян разработал полиномиально сложный (P) метод решения задачи линейного программрования. Но на практике по-прежнему пользуются экспоненциально сложным (NP) симплексным методом.

Кстати, полиномиальный алгоритм для линейного программирования иногда используются, только не Хачияна, а Кармаркара.

[пианист]

Все-таки уточню: Хачиян не придумал эллипсоиды, он доказал полиномиальность.

[Sender]

Urnwestek в сообщении #773062 писал(а):

известны задачи из класса P, для которых доказана оценка $\Omega(n^3).$

Ссылкой не поделитесь?

[nikvic]

Portnov в сообщении #773119 писал(а):

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

Остановлюсь на в).
Давным-давно была придумана конструкция оптимального (с точностью до "степени") алгоритма - некоторый аналог оптимального кодирования в сложности Колмогорова.

Именно, на конкретной NP-задаче запускается процесс поиска решения для (потенциально) всех возможных "решателей" с разделением во времени и разным замедлением. Когда очередной решатель заканчивает работу, его ответ проверяется.

Такой способ исключает в): алгоритм-то у нас есть, мы только не знаем, когда его остановить с уверенностью, что дальше искать решение безнадёжно.

[hazzo]

Vieux в сообщении #773055 писал(а):

4-Вообще как Вы думаете, человеку который нашел такое доказательство стоит сразу опубликовать его или есть более разумный (не рискованный) способ заявить об этом?

Думаю если алгоритм очень эффективный, то разумнее будет:
а) не публиковать сразу или вообще не публиковать;
б) решить с помощью алгоритма некоторые трудные с практической точки зрения задачи, но например, факторизовать RSA-challenges за короткое время или найти простые числа с большим количеством (от 100000) десятичных цифр. Тогда математики и информатики обратят внимание. Только без всяких правонарушений.
в) теперь если нужны репутация и деньги можно сказать, что у Вас есть эффективный полиномиальный алгоритм, например, для SAT или для любой другой NP-полной задачи, усиливая аргумент ссылками на практические результаты.
г) в дальнейшем различные серьезные мат. журналы, компании, гос. учреждения будут пытаться с Вами сотрудничать и тогда Вы решите для себя, что Вам больше нужно. Деньги, известность, репутация или все вместе. Только будьте всегда разумным и осторожным.
Удачи!!!

[Xaositect]

Sender в сообщении #773291 писал(а):

Urnwestek в сообщении #773062 писал(а):

известны задачи из класса P, для которых доказана оценка $\Omega(n^3).$

Ссылкой не поделитесь?

Есть даже явная последовательность задач из $\mathbf{P}$ с неограниченно увеличивающимися экспонентами: Adachi A., Iwata S., Kasai T. Some combinatorial game problems require $\Omega(n^k)$ time

[Pavlovsky]

Vieux в сообщении #773055 писал(а):

Или для института Клея очевидно, что $P\not=NP$?

Совершенно очевидно, что $P\not=NP$. И только безграмотные альты еще ничего не доказав уже беспокоятся, что у них что то украдут.