NP-Complete — Почему Так Сложно?

Выбранный на этой неделе мультфильм xkcd посвящен тайнам NP-полных проблем. Итак, у официанта есть проблемы? Скорее всего, нет. Давайте посмотрим, почему.

Алгоритмы занимают разное количество времени для выполнения своих задач, но что действительно важно в теории сложности, так это то, как они масштабируются.

Проблема коммивояжера упоминается в мультфильме, но если я дам вам пример проблемы, вы, вероятно, сможете решить ее в разумные сроки. Все, что вам нужно сделать, это найти маршрут для продавца, чтобы он посетил каждый город только один раз с общим расстоянием меньше L. (Обратите внимание, что полная проблема требует, чтобы L был минимальным, но это еще более сложная проблема)

Конечно, для нескольких городов это легко — просто разработайте каждый возможный маршрут и выберите маршрут с расстоянием меньше L. Суть проблемы в том, что каждый раз, когда вы добавляете город, количество маршрутов, которые вы должны изучить, становится все больше. Увеличение объема необходимой работы происходит непропорционально очевидному увеличению масштабов проблемы.

Это означает, что рано или поздно вы достигнете точки, когда проблема разумного размера полностью выходит за рамки ваших вычислительных возможностей. Так, например, если я попрошу вас найти кратчайший путь даже между 100 городами, у вас будет много работы.

Но у многих таких проблем есть интересная другая сторона. Например, если я дам вам предлагаемое решение даже проблемы 100 городов, вы можете проверить, что это решение очень быстро — просто подтвердите, что оно посещает каждый город и что пройденное расстояние меньше L.

Это то, что делает проблему NP.

N означает недетерминированный, а P-полиномиальный, и идея заключается в том, что, хотя сложность исходной задачи может расти быстрее, чем любая степень размера (т. Е. Она Растет быстрее, чем любой полином размера), проверка решения, полученного путем угадывания, т. е. недетерминированного, является полиномиальной по размеру задачи.

Именно это сведение к задаче P путем угадывания решения приводит многих к мысли, что NP=P. То есть есть более быстрые решения проблем NP, которые мы просто еще не нашли.

Итак, что такое NP-полные проблемы?

NP-полная задача-это задача, которая может быть преобразована в любую другую NP-задачу за разумный, т. Е. полиномиальный промежуток времени. Таким образом, если у вас есть P-алгоритм для любой NP-полной задачи, то у вас есть P-алгоритм для всех NP-задач и NP=P.

Вы можете думать о NP-полной задаче как об универсальном представителе NP-задач.

Наконец, как насчет NP-сложных проблем?

NP-трудная задача-это любая проблема, не обязательно в NP, которая может быть сведена к NP-полной задаче за разумное, т. е. полиномиальное время. В этом смысле NP-трудные задачи не менее трудны, чем NP-проблемы, но они могут быть сложнее. Например, предположим, что у вас есть экспоненциальное решение NP-трудной задачи, тогда оно может быть преобразовано в экспоненциальное решение NP — задачи (часть полиномиального времени просто поглощается экспоненциальной), и у вас есть экспоненциальное решение NP-задачи-но у проблемы NP может быть другое решение, которое работает в полиномиальное время.

Например, полная проблема коммивояжера, поиск кратчайшего пути, является NP-трудной, потому что она дает вам решение NP-полной проблемы поиска пути короче L. Однако проблема поиска пути меньше L может быть более простой проблемой, чем поиск минимального пути.

Важным моментом здесь является то, что в большинстве случаев они сложнее и, следовательно, образуют еще более сложный класс проблем.

Итак, теперь вернемся к мультфильму xkcd:

(нажмите, чтобы увеличить)

Проблема, которую просят решить официанта, состоит в том, чтобы найти комбинацию пунктов меню, которые стоят ровно 15,05 доллара.

Это версия проблемы рюкзака, которая, как известно, является NP-полной, и поэтому, если проблема достаточно велика, ее решение занимает много времени, но еще раз предлагаемое решение может быть проверено очень быстро.

Так неужели официант обречен провести всю вечность в поисках решения?

Не с меню такого размера, как показано на рисунке. К сожалению, несмотря на самое лучшее намерение перегружать официанта, сомнительно, что это слишком сильно облагало бы его математику бистро.

Но я все еще сомневаюсь, что эту группу ученых-компьютерщиков когда-нибудь накормят.