Гипотеза Римана

[Xaositect]

В $P\neq NP$ тоже почти все верят.

[Dandan]

причем тут проверка простоты к факторизации? Умение проверять числа на простоту в задаче факторизации вам никак не поможет.

[Skipper]

Dandan

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

Добавлено спустя 4 минуты 13 секунд:

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

[Dandan]

Я рад, что вы разобрались в проблеме P = NP, но причем тут гипотеза Римана?

[Skipper]

Притом, что было высказано предположение что гипотеза Римана может привести к угрозе для RSA. Вот и вопрос - каким образом. Для этого нужно решить проблему факторизации. А вы пишете -

>> причем тут проверка простоты к факторизации?

понятно причем?

[Dandan]

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

[Skipper]

вообще то я не думаю, что гипотеза Римана должна помочь задаче факторизации. Я просто хотел обсудить это, т.к. пишут что-то в таком духе.

[Droog_Andrey]

Помню, как в июне 2004-го пытался вникуть в оригинальную работу Де Бранжа:
http://www.primefan.ru/stuff/books/riemannzeta.pdf

Фигушки, не вышло...

Вот здесь можно посмотреть обновлённые статьи:
http://www.math.purdue.edu/~branges/site/Papers

[Профессор Снэйп]

Skipper писал(а):

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

Слово "гипотеза" впечатляет. P=NP --- тоже гипотеза

И даже если такая гипотеза верна, то сведение сколько времени будет занимать? И потом, у полиномов не только степени, но ещё и коэффициенты большими могут быть

[MaximKat]

Skipper в сообщении #198983 писал(а):

А как насчет P=NP? Математики верят больше, что P=NP или что P не равно NP ?

The P=?NP Poll
http://www.cs.umd.edu/~gasarch/papers/poll.pdf

[maxal]

Свежее доказательство на arXiv:
http://arxiv.org/abs/0903.3973

[sceptic]

Вот еще более свежее "доказательство". Но с тем же результатом

[AD]

Может, прикрепить тему? Приятный разговор такой ...

Вот не так давно я слышал про такую штуку - будто бы доказали, что гипотеза Римана эквивалентна полноте какой-то ортогональной системы в $L_2[a,b]$. Никто не в курсе?

Просто первая мысль была - неужели три студента нашей кафедры за недельку не докажут полноту какой-то-там системы?

[shwedka]

AD писал(а):

Может, прикрепить тему? Приятный разговор такой ...

Вот не так давно я слышал про такую штуку - будто бы доказали, что гипотеза Римана эквивалентна полноте какой-то ортогональной системы в $L_2[a,b]$. Никто не в курсе?

Просто первая мысль была - неужели три студента нашей кафедры за недельку не докажут полноту какой-то-там системы?

Результат довольно давний, шведaм, между прочим, принадлежит.
см, например, в
Nikolski, N.К.,Operators, functions, and systems : an easy reading. Vol. 1: Hardy, Hankel, and Toeplitz
Providence: American mathematical society, 2002

http://projecteuclid.org/DPubS?service= ... 1229618750


http://iml.univ-mrs.fr/~balazard/pdfdjvu/11.pdf
http://www.citebase.org/abstract?id=oai ... th/0202141

[Skipper]

Почитал про аналитическое продолжение дзета-функции, что-то непонятно, почему именно такое а не другое.

Добавлено спустя 29 минут 47 секунд:

>>Вот еще более свежее "доказательство". Но с тем же результатом
>>

Это 25 Mar 2009. Ваш пост 29-го. Кто за 4 дня выяснил, что "с тем же результатом"?