NP-полнота задачи комивояжера

[ifoxy]

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

[Профессор Снэйп]

Papadimitriou C.H. — Computational Complexity
Lewis H.R., Papadimitriou C.H. — Elements of the Theory of Computation

[ifoxy]

Спосибо огромное! А в этих кингах есть решение или какие-то подсказки? не подскажете, что мне конкретно тут искать?

[Профессор Снэйп]

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