СЯУ

[stas]

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

Comments

[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.