Карта → город
Беркли
3 события · 5 линий истории математики
-
11972NP-полнота: 21 задача — одна проблема
Гамильтонов цикл, раскраска карты, укладка рюкзака, расписание — двадцать одна задача из разных областей оказалась одной задачей в разных костюмах. Быстрый алгоритм для любой из них дал бы быстрый алгоритм для всех. Есть ли он — вопрос, стоящий в списке задач тысячелетия.
-
2Миллер — 1976, Соловей и Штрассен — 1977, Рабин — 1980Соловей и Штрассен: монетка вместо доказательства
Поворот, ради которого стоило разбираться со случайностью: она оказалась не помехой, а ресурсом. Чтобы узнать, простое ли число, делители искать не нужно — достаточно взять наугад свидетеля и проверить одно равенство по модулю. Составное число случайный свидетель уличает с вероятностью не меньше половины, так что двести попыток делают ошибку менее вероятной, чем отказ процессора. Ответ «да» здесь не доказан, а лишь очень вероятен, — и на этом с тех пор держится всякая выдача ключей.
-
3доклады — 1982, журнальные версии — 1984Блюм, Микали и Яо: подделка, которую не отличить
Настоящей случайности у машины нет: фон Нейман ещё на исходе сороковых назвал состоянием греха попытку получать случайные цифры арифметикой. Ответ, найденный в Беркли: настоящая и не нужна. Достаточно, чтобы короткое случайное зерно разворачивалось в длинную последовательность, которую никакая быстрая программа не отличит от честной монетки, — а это возможно, если существуют задачи, которые легко задать и трудно решить. Случайность впервые определена не через мир и не через описание, а через того, кто смотрит.