Обновить

Гипотеза о вычислительной сложности алгоритмов.

Пусть есть задача (проблема) размера N. Пусть также существует (известен) алгоритм (метод, способ) решить эту задачу за время O(N*N), и существует способ проверки корректности решения за время O(N).
Тогда существует алгоритм решения этой задачи за время O(N*logN).

Пример 1. Сортировка массивов. Существует алгоритм сортировки за время O(N*N). Корректность работы алгоритма сортировки можно проверить за время O(N). Следовательно, существует алгоритм сортировки за время O(N*logN).

Пример 2. Перемножение длинных (больших) целых чисел (миллионы цифр). Их можно перемножить за время O(N*N). Результат можно проверить за время O(N) с некоторой заранее заданной достоверностью, например, 0,999999... . Следовательно, существует алгоритм перемножения чисел за время O(N*logN).

Есть ли контрпримеры? Ищу их.

Теги:
Всего голосов 2: ↑1 и ↓10
Комментарии12

GPT-6 Astra помогла прочесть зашифрованную Enigma немецкую радиограмму 1941 года — над ней бились 21 год

Сотрудник Bloomberg Картер Леффен с помощью GPT-6 Astra расшифровал немецкую военную радиограмму MVUEH от 10 июля 1941 года. Сообщение состояло всего из 82 зашифрованных символов и находилось в коллекции исследовательского проекта CryptoCellar. По словам его куратора, специалиста по Enigma Фроде Вайеруда, попытки подобрать к нему ключ предпринимались с 2005 года — безуспешно.

Иногда эту историю уже пересказывают как «шифр не могли разгадать 83 года», но на самом деле неизвестно, пытался ли кто‑нибудь расшифровать именно эту радиограмму в течение большей части времени после войны. В современный криптоаналитический проект сообщение попало значительно позже. Вайеруд говорит вполне конкретно: MVUEH сопротивлялась попыткам расшифровки с 2005 года.

Леффен дал GPT-6 Astra в режиме Extra High довольно общую задачу — изучить оставшиеся нерасшифрованными сообщения из коллекции CryptoCellar и попробовать взломать одно из них. По рассказу самого Леффена, непосредственно работа модели до нахождения решения заняла около десяти часов. Всё исследование вместе с разбором источников, дополнительными проверками и воспроизведением результата шло 14 и 15 сентября.

GPT-6 Astra помогла прочесть зашифрованную Enigma немецкую радиограмму 1941 года — над ней бились 21 год

Публикации