In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems.
În teoria complexității, versiunea de decizie a PCV (unde, dată fiind o lungime L, sarcina este de a decide dacă graful are un ciclu complet mai scurt decât L) aparține clasei problemelor NP-complete.