I'm asking because it seems that P problems refer to decision problems rather than actually propose a solution.
If you have available a TSP decision oracle -- that is, a function that answers questions of the form "Does directed graph $G$ have a TSP tour of length at most $k$?" in constant time -- then the following algorithm will allow you to construct an actual TSP tour using $O(|E|)$ calls to the oracle, and $O(|E|^2)$ time overall:
- Run a binary search on $k$, calling the decision oracle at each step, to determine $OPT$, the minimal tour length of the original graph $G$. (If necessary, the absence of any Hamiltonian cycle at all can be first tested for by calling the oracle with a very large threshold -- e.g., equal to the sum of all edge weights.)
- If $G$ contains 3 or fewer edges, then stop. (These must form a triangle.)
- Choose an arbitrary vertex $u$ in $G$.
- For each out-edge $uv$ in $G$:
- Create a new graph $G'$, which is the same as $G$ except that the edge $uv$ has been collapsed (specifically: delete vertices $u$ and $v$ and all edges they are incident on, and create a new vertex $x$ that has all of $u$'s incoming edges and all of $v$'s outgoing edges).
- Run the decision oracle on $G'$ with the length threshold $OPT-w(uv)$.
- If the answer is YES, then some optimal solution to $G$ contains the edge $uv$: Replace $G$ with $G'$ and $OPT$ with $OPT-w(uv)$ and go to 2.
- If the answer is NO, then no optimal solution to $G$ contains the edge $uv$: Delete $uv$ from $G$, and continue iterating through other out-edges of $u$ in $G$.
The iterations in the loop beginning at step 4 execute at most $|E|-3$ times. How quickly the graph modification steps (edge collapsing, edge deletion) in each iteration can be performed probably depends on the graph representation used, but they can certainly be done in $O(|E|)$ time each, for $O(|E|^2)$ time overall, which is enough to show the algorithm is polynomial. (Can anyone think of faster $O(|V|)$ or even $O(|1|)$ ways to perform these modifications?)
The above runs on a directed graph $G$. If you have an undirected graph, you can first turn each undirected edge into a pair of opposite-facing directed edges having the same weight, and then run the algorithm as before.