Книга: Золотой билет

Весь боевой арсенал

Весь боевой арсенал

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

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

Оглавление книги