They are proposing an algorithm to solve the travelling salesman problem and this algorithm in essence fixes a set of boolean variables of the form visit city X in step Y. They are however using linear programming which has an efficient algorithm but only constraints the variables to be between 0 and 1, not to be either 0 or 1. With variables constraint to 0 and 1 only one gets integer linear programming which is NP-hard. Nonetheless they claim that their algorithm can solve the travelling salesman problem with a polynomial number of linear constraints and offer $10,000 for a problem instance that can not be solved. Essentially the claim is that they have developed a set of constraints that ensures that the optimum is always at 0 or 1 and never somewhere in between. The claim is almost certainly wrong and it should not be too hard to find a counter example and claim the money.
x, y ∈ { 0, 1 }
Constraints 2x + y ≤ 2
-2x + y ≤ 0
Maximize x + 3y
To win the prize, you will have to do this with something like n⁶ variables and constraints where n is the number of cities in the problem. And I would guess that you might need maybe about 5 to 10 cities to construct a counter example, but that does not mean that you have to actually deal with all the constraint equations, the construction of the weights will do all the work.
But somewhere in between too few and too many edges, there is a critical edge density where the problem undergoes a pretty rapid phase transition from essentially all colorings being valid to only very few colorings being possible and that is where the hard instances are mostly hiding.
Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.
This seems to be something like an escape-hatch to reject any counterexamples.
> An issue attributable to numerical issues (for example, numerical stability and round-off errors) will not be considered as a basis for a valid claim of a counter-example.
So if their algorithm never converges with your input, it's not a counterexample?
>So if their algorithm never converges with your input, it's not a counterexample?
No, if their algorithm never converges when calculated by hand it is a counterexample. If their algorithm never converges only because of rounding behavior in IEEE754 as implemented by Intel, then it isn't a counterexample.
So yeah, there are easier ways for me to make $10k.
As a trivial example, let's say you represent each city by their latitude/longitude encoded as integers, with 0 being ...well 0, and 180,000,000 being 180W. Let's also say you can encode each city's longitude with 0 meaning 0-90W, or 1, meaning 90-180W and its latitude 0 being 0-45N and 1 being 45-90N. The second encoding is a much, much, MUCH easier problem for a large number of cities. By using a small, fixed number of bits, you've effectively capped the size of your input as 4 bits. You just have 4 locations a city might be in; you can solve this approximation with a simple 16 element lookup table. By discarding bits in the city's coordinates, you're approximating the solution, not finding the exact solution.
This is not just a triviality. The dynamic programming algorithm to solve subset sum runs in O(MN) time, where M is the number of integers, and N is the sum you're looking to achieve. Running subset sum on 1,000,000 numbers that you want to add up to 100 is going to run in milliseconds, but running that algorithm on 1,000,000 numbers that add up to 1,000,000,000 is going to take a while. (10,000,000 times as long) Subset sum is NP-complete, but it's only NP-complete because you're not talking about the value of the sum, you're talking about the number of bits it takes to represent the sum. One of the other problems in Karp's NP-completeness paper reduces to subset sum by summing up 1s or 0s shifted by i bits for each element in the input; so if there are 7 elements, the N for subset sum will be on the order of 2^7. If there are 1,000 elements, N for subset sum will be on the order of 2^1,000.
You can approximate subset sum by dividing every number by some constant. So if you want to know which integers of 3,4,5,6,7,8 sum to 12, you can divide everything by 3 and figure out which integers of 1,2,2,2,3,3 sum up to 4. (round up) If you were to take that 1,000 element problem, compute the sum to be some ludicrous integers on the order of 2^1,000, then divide everything by 2^980, and then solve the approximation in O(M * 2^20) time, what have you done? Well you've simply discarded 98% of the inputs. You haven't gained anything by reducing to subset sum and approximated the solution; you could have simply discarded all by 20 of the inputs and solved that with the brute force algorithm, whatever it is.
That's what this paper is doing by handwaving away the low order bits. They're saying you can solve TSP in O(m^k * n^j) time, where m is the number of cities, k and j and some arbitrary fixed constants, and n is the number of bits in the mantissa of your floating point scheme, ie, only if n is a small fixed constant. They've found an approximation of an NP-complete problem, which is something we already have in droves.
Their challenge is a weaker equivalent to: there is a problem that have two types of example: solvable and unsolvable. Their claim is that their program can solve all, including unsolvable! To disprove our claim, provide an input that is unsolvable, along with its solution, and show that we do not find the given solution. The catch is, a problem that is not solvable has by definition, no solution.
In their case, the issue is not that the problem to be submitted has no solution, but that its solution is NP-hard to find. They are basically asking submitters to first find a solver for a NP-hard problem.
Disclaimer: I don’t fully understand the puzzle yet but I am intrigued!
In real world usage, the TSP gets into the thousands of "cities." This would be for things like integrated circuit layouts.
https://arxiv.org/abs/cs/0610125
Have the authors made any attempt to address this criticism?
Tuesdays at 9/8 Central