There is an alternative, equivalent definition of NP languages, through projections of certain polynomially bounded and P-verifiable relations. This is the stri

There is an alternative, equivalent definition of NP languages, through projections of certain polynomially bounded and P-verifiable relations. This is the strict mathematical base for the commonly spread and very valid observation, namely that for a decision problem to be in NP means for its solution to be verifiable in polynomial time. Traveling salesman is in NP. There is no point debating this. Edit: as others have pointed out: traveling salesman in in NP only when it is in its decision version. Otherwise the question does not make sense, as standard complexity classes are defined for decision problems, this is - for languages.