Литература по вопросу из теории вычислительной сложности

[Sender]

Sender в сообщении #1503823 писал(а):

Ну раз мы пытаемся свести оптимизационную задачу к задаче распознавания, то, по-моему, вполне естественно вот эту последнюю и использовать в качестве оракула, нет?

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

[technocrator]

Xaositect, спасибо, поизучаю!

[пианист]

Xaositect
Спасибо.