For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2
There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).
Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ...
After program stops, we check if its output is our witness.
If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.
For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.
Epsilon isn't a problem, as TSP is NP-complete even for integer weights.
Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle).
I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.
I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version)
For another resource see:
https://www.ibm.com/developerworks/community/blogs/jfp/entry...
note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.
Decision version of TSP is NP-complete.
Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P.
(note that it's not true if you replace P with NP, for example)
There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time.
(still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need solutions for known-solvable instances)
First, use binary search to find answer.
Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.
Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.
You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral).
Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.
