One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in $\mathcal{NP}$, as most resources on the internet claim. Let's gather what I know so far:
A decision problem is in $\mathcal{NP}$, if a "yes"-instance is verifyable in polynomial time.
This is an easy definition. E.g. I can see that for the decision problem "is $x$ the maximum of $x_1,\ldots,x_n$?", it is verifyable in $n$ steps whether the answer is correct.
Let's see the formulation of the Travelling Salesman Problem as a decision Problem.
For a simple graph $G$ with costs assigned to each edge, is there a hamiltonian cycle with total cost of at most $\lambda$?
I often read that a solution is verifyable as adding the costs of a tour has polynomial time complexity. The crux: we don't have a tour! We only have the information that there is a tour with total cost $\leq \lambda$.
In my understanding, a decision problem can't "return" the tour as well, so we can't just magically have one for which we just verify the sum of costs.
That leaves me with the question
"Is there a way to construct a tour with a certain value in polynomial time?"
OR
"Is my definition of $\mathcal{NP}$ incorrect?"
Best Answer
You have misunderstood the verifier-based definition of NP. NP is a class of decision problems, but there is an additional requirement that there exists a proof that a "yes" answer is correct and that proof be verifiable in polynomial time. The need for a decision problem and the need for a polynomial time checkable proof are separate requirements.
Note that if you have an oracle that can answer yes/no questions about NP problems, you can use it to construct a proof, be it a Travelling Salesman tour, clique or a variable assignment that satisfies a Boolean formula. This is because all NP problems are downward self-reducible, meaning queries about subproblems of the main problem can be used to prune the search space down to a solution.