נסמן ב-TSP-TI את תת־הקבוצה של TSP, גרסת ההכרעה של בעיית הסוכן הנוסע, שמכילה אך ורק גרפים המקיימים את אי־שוויון…

נסמן ב-$TSP\text{-}TI$ את תת־הקבוצה של $TSP$, גרסת ההכרעה של בעיית הסוכן הנוסע, שמכילה אך ורק גרפים המקיימים את אי־שוויון המשולש (Triangle Inequality).

הוכיחו כי $TSP\text{-}TI$ היא $NP$-קשה.