LINUX.ORG.RU

P?=NP

 , ,


0

1

Вот иногда бывают новости, что кто-то там доказал, что p=np. ЕМНИП, где-то год назад какой-то российский математик якобы доказывал, ещё в толксах было.

Насколько я понимаю суть, если это верно, то например, задача факторизации чисел имеет решение за полиномиальное время. Т.е. современной асимметричной криптографии придёт пушной зверёк и без квантового компьютера на 100500 кубитов.
Так что предлагаю таким математикам, которые утверждают, что доказали P=NP, приводить рабочий алгоритм разложения чисел на простые множители.
Это легко проверить (в отличие от «вечного двигателя», внутри которого, может, негры крутят велосипед). Берём любой открытый ключ RSA, если этим алгоритмом можно получить закрытую часть (за полиномиальное время), значит можно верить и проверять дальше.
А не можешь - твоё доказательство говно, не зависимо от того, что в нём написано (математическая строгость и прочее), и даже не стоит тратить время на его проверку.

Это если доказательство конструктивное и дает алгоритм сведения хотя бы одной задачи из класса NP в класс P.

buddhist ★★★★★
()

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

не придет. Ибо реальная констанста в полиноме может быть около 100500.

dikiy ★★☆☆☆
()

Да, как я и думал. Разложение простых чисел решается за полиномиальное время. Алгоритм известен с 2002 года. AKS-Algorithm.

dikiy ★★☆☆☆
()

Берём любой открытый ключ RSA, если этим алгоритмом можно получить закрытую часть (за полиномиальное время)

Полиномиальное - не значит быстрее нынешних алгоритмов на любых данных. Может быть, для 2048битного ключа этот алгоритм будет выполняться 100500 лет, а ты так берёшь и бездумно отвергаешь доказательство одной из важных проблем математики.

unC0Rr ★★★★★
()
Ответ на: комментарий от TheAnonymous

Это не разложение на множители, а проверка простоты

да, точняк. Разложение сложнее.

dikiy ★★☆☆☆
()
Ответ на: комментарий от unC0Rr

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

TheAnonymous ★★★★★
() автор топика

российский математик

То же самое, что британские учёные. Даже смешнее.

EXL ★★★★★
()

где-то год назад какой-то российский математик якобы доказывал, ещё в толксах было

1)не в толксах, а в development 2)не математик, а электрик

registrant ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.