“P = NP” Polynomial-Sized LP Models for Hard Cops
tsplp.research.uconn.eduAfter 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.
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.x, y ∈ { 0, 1 } Constraints 2x + y ≤ 2 -2x + y ≤ 0 Maximize x + 3yTo 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.
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.
I see article here which directly criticizes the whole approach while giving counterexamples for original (2006 version) of the paper:
https://arxiv.org/abs/cs/0610125
Have the authors made any attempt to address this criticism?
The problem with the challenge is that one must provides a solution to the problem along with the problem. IOW, you must have a solver that can solve your input problem.
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.
If the counterexample is small can you just throw compute at it and swallow that it wont be solved in polynomial time but it will be solved.
Disclaimer: I don’t fully understand the puzzle yet but I am intrigued!
With what budget? P versus NP is our terrible rough estimate for budgeting things like compute time. If you think you have a known NP case where do you even start to plan a budget (for grant proposals if nothing else) on how much computing resources to "just throw at it"?
There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.
Can't you construct a problem from a known solution? To use an analogy, I can't factor arbitrarily large numbers in polynomial time, I'd doubt anyone else can either. But I can multiply large prime numbers together in polynomial time, so I can give someone a large composite and its factorization, because I started with the primes.
Even if this paper is correct, the approach is not practical. From table 1 in section 6.2, the LP representation of a 25-city TSP requires 24,580,032 variables and 3,643,825 constraints. Merely formulating that model will require significantly more time than fully optimizing a TSP of that size using an assignment or 2-matching relaxation and adding subtour elimination constraints as they are violated. The former will likely take seconds (or maybe minutes) at that size, while the latter can be accomplished in milliseconds.
That table of values looks like it's growing exponentially. By the time they reach 70 cities, they will be into a trillion variables, which is not practical.
In real world usage, the TSP gets into the thousands of "cities." This would be for things like integrated circuit layouts.
"exponentially" is not something you can just colloquially throw about in this sort of discussion. The numbers are bounded by n^6, and the whole point of the table is that it seems like it's growing at even less than that.
If so how can they claim this is in P time?
“Hard COPs”, not “Hard Cops”. Is this HN's auto-capitalizing?
Maybe the police are aroused by computational problems
> A failure due to numerical difficulties of computers is not considered to be a counter-example.
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?
How so? It is a theoretical CS paper, what do hardware limitations have to do with it.
>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.
Which means in order to collect you need to find a counterexample and solve it (a np hard problem) by hand.
So yeah, there are easier ways for me to make $10k.
Well you could computer generate counterexample by computer but hand verify that it isn't a hardware issue. Making 10k working for minimum wage is probably less effort and more likely to pay off.
The authors have this P=NP 'proof' for more than a decade. When the trisector comes[0] and offers you money for finding a mistake you are not going to see any money
[0] http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf
Fundamentally, because big-O notation operates on the size of the input, not the number of elements in the input.
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.
Hard Cops: Chicago Streets
Tuesdays at 9/8 Central