Описание тега np-complete

Классический метод атаки NP-полных задач - попытаться доказать, что P = NP. Как только будет доказано, что решение PTIME существует по крайней мере для одной NP-полной проблемы, его можно использовать для решения всех остальных посредством сокращения.

Это активная область исследований. Сообщения ACM Volume 52, Number 9 (2009), Pages 78-86: The Status of the P vs NP Problem дают хороший обзор проблемы и текущих подходов к ее решению. (Статья находится в свободном доступе здесь.)

Кроме того, есть несколько подходов, которые можно использовать для получения полезных, хотя и не оптимальных, решений NP-полных проблем на практике:

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