Доказательство равенства P и NP

[AK-47]

Собственно хотел спросить, доказано ли равенство или неравенство классов сложности P и NP?
Что нового есть по этой теме?

[ShMaxG]

А я думал, что здесь появилось доказательство равенства, а то все ВТФ, да ВТФ...

Нет, до сих пор не доказано ни равенство, ни неравенство. А что конкретно хотите обсудить?

[AK-47]

ShMaxG в сообщении #266100 писал(а):

Нет, до сих пор не доказано ни равенство, ни неравенство. А что конкретно хотите обсудить?

Значит есть шанс получить милион долларов осталось только доказать...

А может быть есть какие-нибудь перспективные направления по этой теме?

[Ираклий]

AK-47 в сообщении #266129 писал(а):

Значит есть шанс получить милион долларов

Если вдруг докажите равенство, то есть шанс (неплохой) стать невыездным..

ShMaxG в сообщении #266100 писал(а):

А я думал, что здесь появилось доказательство равенства, а то все ВТФ, да ВТФ...

У меня была книжка под названием "Полиномиальные алгоритмы решения переборных задач". Выбросил бяку.

[AK-47]

Ираклий в сообщении #266171 писал(а):

Если вдруг докажите равенство, то есть шанс (неплохой) стать невыездным..

Не понял, почему?

Ираклий в сообщении #266171 писал(а):

У меня была книжка под названием "Полиномиальные алгоритмы решения переборных задач". Выбросил бяку.

Не нашел такой книжки в электронном виде. А что там было не так?

[ShMaxG]

AK-47
Ну вообще NP-полных задач куча, на самые разные темы и объекты. Выбирайте любую и сводите ее к полиномиальной. В голову приходит известная книга Кормена "Алгоритмы: построение и анализ". Там много чего написано на эти темы.

[Maslov]

ShMaxG в сообщении #266191 писал(а):

Ну вообще NP-полных задач куча, на самые разные темы и объекты.

Вот здесь их около 300 штук перечислено: Гэри М., Джонсон Д. — Вычислительные машины и труднорешаемые задачи
И если хотя бы одну из них за полиномиальное время решить, такое начнётся ...

[AK-47]

ShMaxG в сообщении #266191 писал(а):

AK-47
Ну вообще NP-полных задач куча, на самые разные темы и объекты. Выбирайте любую и сводите ее к полиномиальной. В голову приходит известная книга Кормена "Алгоритмы: построение и анализ". Там много чего написано на эти темы.

Выбрал задачу коммивояжера

[Maslov]

AK-47 в сообщении #266198 писал(а):

Выбрал задачу коммивояжера

Держите в курсе

[Ираклий]

AK-47 в сообщении #266187 писал(а):

Не понял, почему?

Чуть ли ни вся криптография основана на так называемых "необратимых функциях". Под этим имеют в виду функцию, для которой известен полиномиальный алгоритм вычисления, а для вычисления обратной функции такого алгоритма не найдено. На предположении, что такого алгоритма вообще нет, основана надежда на надежность многих шифров и защитных систем. Равенство P=NP поставит под удар весьма богатых и влиятельных людей этого мира.

AK-47 в сообщении #266187 писал(а):

Не нашел такой книжки в электронном виде. А что там было не так?

Честно говоря, искать ошибку в ней мне было лень.

[AK-47]

Maslov в сообщении #266205 писал(а):

Держите в курсе

Договорились.

Ираклий в сообщении #266208 писал(а):

Чуть ли ни вся криптография основана на так называемых "необратимых функциях". Под этим имеют в виду функцию, для которой известен полиномиальный алгоритм вычисления, а для вычисления обратной функции такого алгоритма не найдено. На предположении, что такого алгоритма вообще нет, основана надежда на надежность многих шифров и защитных систем. Равенство P=NP поставит под удар весьма богатых и влиятельных людей этого мира.

На сколько я понял из статьи Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография, доказательство равенства P и NP должно не сильно повлиять на криптографию.

[Ираклий]

AK-47 в сообщении #266212 писал(а):

На сколько я понял из статьи Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография, доказательство равенства P и NP должно не сильно повлиять на криптографию.

Как раз наоборот, автор статьи убежден в том, что если выяснится, что P=NP, то

Цитата:

криптография, и теоретическая и практическая, по существу, прекратят свое существование

Далее автор статьи опровергает некоторые возражения, которые могут возникнуть в связи с этим тезисом.

[AV_77]

Ираклий в сообщении #266219 писал(а):

Как раз наоборот, автор статьи убежден в том, что если выяснится, что P=NP, то

Цитата:

криптография, и теоретическая и практическая, по существу, прекратят свое существование

Далее автор статьи опровергает некоторые возражения, которые могут возникнуть в связи с этим тезисом.

Криптография с открытыми ключами - да, прекратит. А классические алгоритмы останутся.

[AK-47]

Ираклий в сообщении #266219 писал(а):

Как раз наоборот, автор статьи убежден в том, что если выяснится, что P=NP, то

Цитата:

криптография, и теоретическая и практическая, по существу, прекратят свое существование

Далее автор статьи опровергает некоторые возражения, которые могут возникнуть в связи с этим тезисом.

Перечитал еще раз. Да, наверное вы правы

Даже и не знаю, стоит ли теперь этим заниматься. Хотя, с другой стороны, если P=NP, то рано или позно все равно кто-нибудь это докажет.

[Руст]

Никакой угрозы от $P=NP$ для криптографии нет. Полиномиальное не значит, что линейное. Даже если проверка занимает $n$ операций, а взлом открытого ключа $n^2$ операций, то и на этом можно строит криптографию. Вполне возможно, что $P=NP$. Однако, для решения некоторых задач скорее всего требуется $O(n^k)$ операций, где $k$ порядка 10 или более.