P = NP
P = NP — мощная математическая задача, которая вопрошает — равны ли классы сложности задач P и NP или нет.
Описание[править]
Сложность алгоритма P означает, что время на решение возрастает пропорционально многочлену, в то время как NP значит, что само решение задачи крайне сложное, но вот проверить верность решения можно за время P. Соответственно встаёт вопрос, есть ли быстрое решение для задач класса NP.
Например, к P-алгоритмам относятся сортировка массива, поиск кратчайшего пути в графе, проверка простоты числа. NP-задачи же являются гораздо более сложными и яростными, например задача о коммивояжёре, задача о рюкзаке, раскраска графа в 3 цвета, судоку. Решение хотя бы одной такой задачи в P докажет равенство этих классов.
Ещё в 1956 году Курт Гёдель в письме к Джону фон Нейману спросил, можно ли задачи, для которых решение легко проверить, решать существенно быстрее. Однако несмотря на все усилия математиков, которые властно изучают сей вопросыч, никаких подвижек в этом не состоялось, что в целом не так и плохо, поскольку есть весьма потужный нюанс.
Если удастся доказать равенство классов, то все NP-полные задачи станут эффективно решаемыми. Современная криптография полностью окажется в афедроне, любой шифр можно будет взломать за полиномиальное время. Также компьютер сможет автоматически находить доказательства теорем разумной длины.
Однако вероятнее всего полагается, что это просто разные классы и свести NP к P невозможно. Тогда придётся, как и сейчас, использовать приближённые алгоритмы или эвристики для задач на оптимизацию, которые работают властно и долгое, и соответственно прогностическая возможность машинерии классических архитектур — какая-то слабенькая, что ли. Мудрецы же поговаривают, что это лишь оттого, что профанам впаривают узкую в своей концептуальности информатику: цифровую (не аналоговую), да ещё и прущую через так называемое бутылочное горлышко фон Неймана. А вот в потаённых элитных датацентрах ZOG давно прочухали за параллелизм, и оттого вся криптография, в т. ч. блокчейн, это заведомый лохотрон. Но это ведь лишь конспирология, правда?… right?
