Бесполезные вопросы

Станет легче, но не намного.

From:

wordsmsdnua.livejournal.com

с чего бы?

From:

pyka-npu3paka.livejournal.com

Равенство классов P и NP накроет шифры гораздо быстрее;)

From:

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

From:

pyka-npu3paka.livejournal.com

вроде любой перебор по времени занимает больше чем решение по алгоритму, не?)

From:

Зависит от алгоритма. Вдруг кто-нибудь откроет полиномиальный алгоритм с временем работы n^100^100^100. Теоретически он эффективнее прямого перебора, но для всех практических значений n перебор гораздо быстрее.

From:

blackyblack.livejournal.com

Чем вам перебор множителей не формула определения простого числа? Тут вопрос не в существовании формулы или алгоритма, а в сложности этого алгоритма. Сложность решета Эратосфена: O(n log log n). А суть вашего вопроса, по всей видимости, в том, что было бы, если бы придумали алгоритм с константной сложностью.

From:

Формулы для простых чисел давно известны. Даже в википедии в статье "простое число" приведен многочлен множество положительных значений которого, при неотрицательных значениях параметров совпадает с множеством простых чисел. И вообще вычисления "по формуле" ничем принципиально не отличаются от вычислений "по алгоритму". Не так давно был открыт тест на простоту, с полиномиальной сложностью от длины числа. То-есть он требует C(log n)^k операций. Это несомненно красивый результат, но мир он пока никак не изменил.

From:

stairian.livejournal.com

Это не совсем та формула, которую имел в виду автор. В той формуле просто получается множество всех простых чисел. Что вообще говоря представляет не особо большой интерес.

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

From:

Есть очень простая и абсолютно бесполезная формула. А именно, как доказали в 1947 году, существует число Х, такое что [Х^(3^n)] является простым числом. Квадратные скобки здесь означают целую часть числа.

From:

что изменилось в мире от того, что доказали теорему ферма? вот примерно такой же силы потрясение ждет мир, когда разрешат проблему гольдбаха или найдут формулу простых чисел :)

From:

Простые числа более юзабельны - например, в шифровании.

From:

вы правда думаете, что мир перевернется, если методы шифрования станут более эффективными?

From:

Мир вряд ли перевернётся, но может пошатнуться, если существующие методы шифрования станут МЕНЕЕ эффективными.

From:

это только поначалу :)

From:

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

From:

значит, когда я писала первый комментарий в ветке, настрой у меня был весьма оптимистичный :)

From:

В этом году, судя по всему, доказали тернарную гипотезу Гольдбаха. То-есть любое нечетное число >6 является суммой трех простых. Это тот самый вопрос, который Гольдбах задал Эйлеру.

From:

к сожалению, не слежу за новостми математики :) разве теорему гольдбаха не доказывали уже раз этак 10, а то и 11? :)

From:

Статью опубликовал вполне серьезный математик. И доказательство разумной длины, кажется 100 с чем-то страниц. Конечно вероятность ошибок есть всегда. Чем дело кончилось не знаю, я тоже за новостями не слежу.

From: