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.
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.
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.
Comments
The challenge has been up for a year now. Is the counter example too hard to find and not worth $10,000?
Another comment links to a paper explaining how to construct counter examples. To give an idea, here is a very simple example.
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.
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.
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.