To clarify your last point, P and NP are classes of 'decision' problems, i.e. problems for which we have a yes/no answer. TSP is commonly formulated as a combin

To clarify your last point, P and NP are classes of 'decision' problems, i.e. problems for which we have a yes/no answer. TSP is commonly formulated as a combinatorial OPTIMIZATION problem The decision version of TSP would be formulated as: Given a complete graph G and a budget b, decide if there exists a path that visits each node and has cumulative weight less than b. If you have a solver for decision TSP, then you can solve the optimization version of TSP by performing binary search on the budget b. I'm glossing over some details, but there's a clearer explanation on how to solve search problems with an oracle for decision problems in Sipser.