It's true that my formulation isn't completely specified but the basic idea still works because if you have a decision function for an NP problem you can find a solution (assuming at least one exists) with one call to D per bit of the solution.
So to actually solve the optimization version you would need two iterations/recursions around the call to D. The inner iteration finds a solution with the desired property, ie. cost <= C and the outer one does the binary search over C. Overall it still reduces to a number of calls to D that is polynomial in the number of bits used to represent the problem, including those used to represent the weights.
The problem with the original blog post is that while the author states correctly that the TSP optimization problem is NP hard rather than NP complete because it doesn't have the form of an NP problem, he doesn't mention that it is also NP easy and therefore NP-equivalent (see last line in this Wikipedia article):
So to actually solve the optimization version you would need two iterations/recursions around the call to D. The inner iteration finds a solution with the desired property, ie. cost <= C and the outer one does the binary search over C. Overall it still reduces to a number of calls to D that is polynomial in the number of bits used to represent the problem, including those used to represent the weights.
The problem with the original blog post is that while the author states correctly that the TSP optimization problem is NP hard rather than NP complete because it doesn't have the form of an NP problem, he doesn't mention that it is also NP easy and therefore NP-equivalent (see last line in this Wikipedia article):
http://en.wikipedia.org/wiki/NP-equivalent