Ironically enough, I think this guy misunderstands TSP. I wrote this comment on his blog:
Let's define a new problem, TSP-cost-optimize, which returns the cost of the best Hamiltonian. It's NP-Complete, because it reduces to TSP-decide: Just do a binary search on the space of possible scores; even if that space is exponential, we're fine, since binary search runs in the log of the size of the space.
TSP-cost-optimize's certificate can be the steps of the binary search; that will be polynomial in size, since it's a polynomial number of TSP-decide certificates, and you can verify it in polynomial time.
Given TSP-cost-optimize, I can in fact provide a polynomial-time-verifiable certificate for the result of TSP-optimize: The result of TSP-cost-optimize on the same graph! So under your definition of NP, TSP-optimize is in fact in NP. (This also makes sense if you use the non-deterministic Turing machine definition of NP.)
What's not clear to me is whether given the result of TSP-cost-optimize, you can actually find a shortest path in polynomial time. But I expect you probably can.
I guess you could find the shortest path by iteratively deleting an edge and checking whether the best cost has got worse. If it does get worse, then put that edge back in and try deleting another edge. If it does not get worse, then permanently delete that edge.
I think this should terminate (after trying all edges once each) with an example of the shortest path (that consists of all remaining edges).
The binary search is not a reduction, because you need to use TSP-decide a polynomial number of times (and for a reduction you reduce to one problem instance). What you show is that your problem TSP-cost-optimize is in FP^NP (the class of function problems solvable in polynomial time with the help of an NP oracle).
Let's define a new problem, TSP-cost-optimize, which returns the cost of the best Hamiltonian. It's NP-Complete, because it reduces to TSP-decide: Just do a binary search on the space of possible scores; even if that space is exponential, we're fine, since binary search runs in the log of the size of the space.
TSP-cost-optimize's certificate can be the steps of the binary search; that will be polynomial in size, since it's a polynomial number of TSP-decide certificates, and you can verify it in polynomial time.
Given TSP-cost-optimize, I can in fact provide a polynomial-time-verifiable certificate for the result of TSP-optimize: The result of TSP-cost-optimize on the same graph! So under your definition of NP, TSP-optimize is in fact in NP. (This also makes sense if you use the non-deterministic Turing machine definition of NP.)
What's not clear to me is whether given the result of TSP-cost-optimize, you can actually find a shortest path in polynomial time. But I expect you probably can.