Hacker News Reader

Comment by danbruc | Hacker News Reader

After skimming the site and the paper this would be my TL;DR.

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.

View on HN

The challenge has been up for a year now. Is the counter example too hard to find and not worth $10,000?

If there are counter examples, but they’re hard to find, this is still pretty interesting — it might meant we could say “most instances of an NP class of problem can be solved in P”.

It is often the case that many instances of problems in NP are easy to solve. Take vertex 3-coloring - color the vertices of a graph with three different colors such that vertices connected by an edge have different colors. If your graph has only a few edges, then you can essentially color each vertex however you want as there are only a few constraints imposed by the few edges and in consequence there are many possible colorings. If your graph has many edges, then there is often only one way to color each vertex because of the constraints imposed by the many edges and in consequence there might only be one or a few possible colorings.

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.

We’ve known a less formal version of this for a long time though. People use SAT solvers because most of the time they work very quickly even though SAT is an NP problem.

You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet. Then add 2SAT (in POLY) and encode it using an alphabet with four letters. If you chose a random instance of length n, the probability it is from SAT is less than 1/2^n.

Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.

Another comment links to a paper explaining how to construct counter examples. To give an idea, here is a very simple example.

  x, y ∈ { 0, 1 }

  Constraints   2x + y ≤ 2
               -2x + y ≤ 0

  Maximize      x + 3y

You can easily check that y = 0 must hold, for y = 1 one of the constraints gets violated whether you have x = 0 or x = 1. So the optimum is x = 1 and y = 0 with a value of 1. If we drop the integer constraint and have x, y ∈ [0, 1], then you will find that x = 0.5 and y = 1 also satisfies both constraints - together with many more pairs - and the optimum value is 3.5.

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.

Take a bunch of hard cases of a known NP-complete problem, reduce it to TSP, then solve them all in polynomial time using your polynomial TSP solver. QED.

You can solve the integer case via branch and bound: solving the relaxed linear problem and then in a tree search constraining integer variables to be 0/1. Potentially they're doing something equivalent to that?

But this leads to an exponential time algorithm.

If the claim were true that the solution is always integer, then one could use a poly-time LP solver.

What if you use 0.0000000000000001 and 1-that?

Then you don't get the optimal integer solution, which can (in general) be arbitrarily far away from the optimal real solution.

Reply on news.ycombinator.com