СЯУ

[stas]

Оказывается, существует полиномиальный детерминистский алгоритм определения простого числа, а мне это было до сего дня неизвестно. Как выучил Миллера-Рабина, так и пребывал в уверенности, что только вероятностными методами достижимо.

Comments

[spamsink]

Я смог вспомнить, где я это в свое время прочитал (но оно уже успело из активной памяти испариться): http://it.slashdot.org/story/02/08/07/0151216/turns-out-primes-are-in-p

[stas]

Вот, а я как-то пропустил, а сегодня слушаю лекцию и там заявляют, что создание AKS намекает на то, что BPP = P и тут я осознаю, что со студенческих лет мои знания сильно устарели.

[yyi.livejournal.com]

just curious, what lecture sees such a hint?
my intuitions on the topic are also way out of date, but I'd say that this hint is not much stronger than linear programing in P hinting that P=NP.

[stas]

There were other examples, but in general primes was very famous problem that was BPP but not P, so when P solution was finally found, those that suspect BPP = P took it as a hint it may indeed be true. Of course, it's not a proof - it's just a kind of side note, and there are still BPP problems that don't have P solutions, but it is said that their number is decreasing, so there might be indeed time when no such problems would remain. Which also wouldn't be, strictly speaking, a proof that BPP = P but for all practical purposes it would be as if it were true.

[yyi.livejournal.com]

but what was the lecture in which this comment was made, I am curious? and by whom it was made?
thanks!

[stas]

https://class.coursera.org/randomness-001
Don't remember the exact lecture there, but somewhere in Week 3.

[glocka.livejournal.com]

А зачем проверять, если можно просто заглянуть, есть ли данное число в таблице простых чисел полученных с помощью многочлена, перечисляющего множество простых чисел (http://dxdy.ru/topic13827-45.html)?

[stas]

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

[glocka.livejournal.com]

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

[stas]

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

[glocka.livejournal.com]

Т.е. как "зачем"?! Для Guinness World Records, конечно.