Почему P = NP настолько важен, что гарантирует приз в 1 миллион долларов?
P против NP. Это вообще разрешимо?
Это одна из семи Задач тысячелетия, выбранных Институтом математики Клэя, каждая из которых имеет приз в размере 1 000 000 долларов США за первое правильное решение. Это самая недавно задуманная проблема из семи (в 1971 году), и к тому же ее легче всего объяснить (надеюсь).
О чем это все?
Прежде чем мы углубимся, я надеюсь, что можно с уверенностью предположить, что те, кто щелкнул эту статью, имеют некоторый опыт программирования и некоторое представление об алгоритмах и их времени выполнения (временная и пространственная сложность). Я не буду вдаваться в подробности технических деталей, но предоставлю некоторую предысторию тем нетехническим людям.
Основные идеи, которые нужно знать людям, не занимающимся программированием
(Те, кто знаком со сложностью времени и пространства, могут пропустить этот раздел)
- Алгоритмы - это просто набор инструкций, написанных на языке программирования
- Алгоритмы - это «мозг» компьютерных программ. Они очень важны для решения наших повседневных проблем, таких как маршрутизация транспортных средств, сворачивание белков, сортировка, поиск простых чисел, поиск по графам и т. д.
- У каждого алгоритма есть временная и пространственная сложность - это, по сути, более крутой с технической точки зрения способ сказать, что каждый алгоритм требует некоторого времени для выполнения и занимает некоторое количество памяти на нашем компьютере при выполнении.
- Полиномиальное время идет медленно. Говоря о временной сложности (т. е. о том, сколько времени требуется алгоритму для выполнения), сообщество программистов измеряет время, которое требуется алгоритму, в зависимости от размера входных данных n. . Математическая нотация, которая описывает ограничивающее поведение функции, когда аргумент стремится к определенному значению или бесконечности, называется нотацией Big O. Как правило, любой алгоритм, который выполняется за полиномиальное время (т.е. занимает n ^ k времени при вводе размера n), считается медленным, но все же «принят» сообществом как верхний предел. Все, что медленнее, считается непригодным для использования сообществом программистов, поскольку затраченное время слишком быстро масштабируется по сравнению с размером ввода.
Так в чем же тогда состоит проблема P и NP?
Для записи, статус-кво таков: P ≠ NP.
P (полиномиальное время) относится к классу задач, которые могут быть решены алгоритмом за полиномиальное время. Проблемы в классе P могут варьироваться от чего угодно, например, умножения до поиска наибольшего числа в списке. Это относительно «легкий» набор проблем.
NP (недетерминированное полиномиальное время) относится к классу задач, которые могут быть решены за полиномиальное время на недетерминированном компьютере. По сути, это еще один способ сказать: «Если у меня неограниченная вычислительная мощность (т.е. столько компьютеров, сколько мне нужно), я могу решить любую проблему за полиномиальное время». Более интуитивно, однако, это относится к классу проблем, которые в настоящее время не имеют возможности найти достаточно быстрый (полиномиальное время) ответ, НО можно быстро проверить (за полиномиальное время), если предоставить решение. к проблеме. Термин «проверено» здесь означает, что можно проверить правильность предоставленного решения.
Очевидно, что, исходя из приведенного выше определения, P ⊆ NP. Давайте рассмотрим пример, чтобы проиллюстрировать эту абстрактную проблему.
Один из наиболее распространенных, но эффективных примеров - Судоку. Учитывая неразрешенную сетку судоку (например, 9 x 9), алгоритму потребуется изрядное количество времени, чтобы решить ее. Однако, если сетка 9 x 9 увеличится до сетки 100 x 100 или 10 000 x 10 000, время, необходимое для ее решения, увеличится экспоненциально, потому что сама проблема становится значительно сложнее. Однако, учитывая решенную сетку судоку (9 x 9), довольно просто проверить, что конкретное решение действительно правильное, даже если размер увеличивается до 10 000 на 10 000. Это будет медленнее, но время проверки решения увеличивается медленнее (полиномиально).
Есть много других задач NP, в том числе проблема ранца и проблема коммивояжера, и они похожи тем, что их трудно решить, но быстро. проверять. Основная проблема, которую мы здесь пытаемся решить:
Означает ли возможность быстрого распознавания NP правильных ответов, что есть еще и быстрый способ их найти?
Если это так (например, P = NP), это может сильно изменить то, как мы смотрим на эти NP проблемы , потому что это означает, что есть быстрый способ решить все эти проблемы, но мы еще не смогли понять, как это сделать.
Если это недостаточно сложно, давайте приправим его.
NP-Complete и NP-Hard
Среди этих NP проблем есть король всех проблем, которые исследователи называют проблемами NP-Complete. Формально это набор проблем, для каждой из которых любая другая NP проблема может быть уменьшена (рассматривается ниже ) за полиномиальное время, решение которого еще можно проверить за полиномиальное время. Это означает, что любая проблема NP может быть преобразована в проблему NP-Complete.
Неформально они являются «самой сложной» из проблем NP. Таким образом, если любая одна NP-Complete задача может быть решена за полиномиальное время, то каждые NP-Complete может быть решена за полиномиальное время, и каждая проблема в NP может быть решена за полиномиальное время (т.е. P = NP). Самый известный пример - задача коммивояжеров.
Также существует набор проблем, называемых проблемами NP-Hard. Эти задачи не менее сложны, чем задачи NP, но без условия, требующего решения за полиномиальное время. Это говорит о том, что проблемы NP-Hard не обязательно могут быть частью класса NP. Примером может служить решение шахматной доски - учитывая состояние шахматной доски, почти невозможно сказать, является ли данный ход в данном состоянии на самом деле оптимальным. Формально не существует алгоритма полиномиального времени для проверки решения проблемы NP-Hard.
Если мы сложим их вместе, проблема NP-Complete подразумевает, что это NP-Hard, но NP-Hard НЕ означает, что это NP-Complete.
Определение NP-полноты
Проблема L считается NP-Complete, если:
- L NP-Hard
- L принадлежит НП
Схема ниже (фокус на левой стороне) должна прояснить ситуацию.
Подождите, что означает сокращение A до B?
Сокращение составляет основу NP-полноты.
Неформально проблема L1 может быть сведена к другой проблеме L2, если:
- Любой экземпляр L1 можно смоделировать как экземпляр L2
- Решение последнего обеспечивает решение первого и наоборот.
Чтобы понять это интуитивно, можно представить себе это как таковое:
Если L1 сводится к L2, L1 должен быть САМЫМ жестким, как L2. И наоборот, L2 должен быть ПО МЕНЬШЕЙ жесткости, чем L1.
Математически это обозначается как: L1 ≤p L2 (читается как «L1 полиномиально сводится в L2 ”).
Что произойдет, если P на самом деле равно NP?
Теперь, когда мы определили все эти разные термины, возникает более важный вопрос: «Почему все это вообще имеет значение?». Решение этой проблемы может иметь серьезные последствия не только для академических кругов, но и для практических целей. Это включает:
- Криптография. От множества паролей, которые мы храним, до ПИН-кода, который мы используем для банкомата, мы полагаемся на эти коды в своей повседневной жизни, потому что их легко проверить, но трудно взломать людям.
- Маршрутизация транспортных средств. Транспортные и логистические перевозки будут оптимизированы по всему миру, что повлияет на многие отрасли, от транспорта до электронной коммерции и производства.
- Сворачивание белка - понимание или прогнозирование того, как данная последовательность аминокислот (белок) будет сворачиваться, чтобы сформировать свою трехмерную форму, поможет во многих областях, таких как создание лекарств и, возможно, даже в лечении рака.
Заключительные замечания
Для меня я больше прагматик, чем идеалист. Я стою на той стороне забора, что P не равно NP и, вероятно, никогда не будет. Как бы мне ни хотелось раскрыть лекарство от рака (с помощью быстрого сворачивания белка) или быстрого движения транспортных средств, я считаю, что мир должен быть таким же сложным, как и сейчас. Компании существуют потому, что они конкурируют друг с другом, чтобы найти лучший (но никогда не лучший) способ решения этих проблем. Эти неразрешимые проблемы движут нашей экономикой и миром.
Если действительно существует решение этой проблемы, сложность проблемы гарантирует денежный приз в размере, намного превышающем 1000000 долларов США.
Поддержите меня! - Если вам нравится мой контент и вы не подписаны на Medium, рассмотрите возможность поддержки меня и подписки по моей реферальной ссылке здесь (ПРИМЕЧАНИЕ: часть ваших членских взносов будет распределена мне как реферальные взносы).
