7 ms·

“P = NP” Polynomial-Sized LP Models for Hard Cops

52 points by mikk14 4y ago

tempodox 4y ago
“Hard COPs”, not “Hard Cops”. Is this HN's auto-capitalizing?
- moss2 4y ago
  Maybe the police are aroused by computational problems
ghordynski 4y ago
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 https://arxiv.org/abs/cs/0610125 Have the authors made any attempt to address this criticism?
danbruc 4y ago
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.
- quickthrower2 4y ago
  What if you use 0.0000000000000001 and 1-that?
  - adrianN 4y ago
    Then you don't get the optimal integer solution, which can (in general) be arbitrarily far away from the optimal real solution.
- missingdays 4y ago
  The challenge has been up for a year now. Is the counter example too hard to find and not worth $10,000?
  - musicale 4y ago
    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.
  - onos 4y ago
    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”.
    - danbruc 4y ago
      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.
    - TimPC 4y ago
      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.
    - Gehinnn 4y ago
      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.
- zelos 4y ago
  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?
  - coliveira 4y ago
    But this leads to an exponential time algorithm.
  - throw_pm23 4y ago
    If the claim were true that the solution is always integer, then one could use a poly-time LP solver.
ryan-nextmv 4y ago
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.
- quickthrower2 4y ago
  If so how can they claim this is in P time?
- antiquark 4y ago
  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.
  - pxx 4y ago
    "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.
antiquark 4y ago
> 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?
- stonemetal12 4y ago
  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.
  - blamestross 4y ago
    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.
    - stonemetal12 4y ago
      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.
      - ithinkso 4y ago
        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 http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf
  - 4y ago
jdlyga 4y ago
Hard Cops: Chicago Streets Tuesdays at 9/8 Central
pierrebai 4y ago
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.
- quickthrower2 4y ago
  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!
  - WorldMaker 4y ago
    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"?
    - danbruc 4y ago
      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.
deleted 4y ago
[deleted]

52 points by mikk14 4y ago

tempodox 4y ago

“Hard COPs”, not “Hard Cops”. Is this HN's auto-capitalizing?

moss2 4y ago
Maybe the police are aroused by computational problems

ghordynski 4y ago

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 https://arxiv.org/abs/cs/0610125 Have the authors made any attempt to address this criticism?

danbruc 4y ago

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.

quickthrower2 4y ago
What if you use 0.0000000000000001 and 1-that?
- adrianN 4y ago
  Then you don't get the optimal integer solution, which can (in general) be arbitrarily far away from the optimal real solution.
missingdays 4y ago
The challenge has been up for a year now. Is the counter example too hard to find and not worth $10,000?
- musicale 4y ago
  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.
- onos 4y ago
  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”.
  - danbruc 4y ago
    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.
  - TimPC 4y ago
    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.
  - Gehinnn 4y ago
    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.
zelos 4y ago
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?
- coliveira 4y ago
  But this leads to an exponential time algorithm.
- throw_pm23 4y ago
  If the claim were true that the solution is always integer, then one could use a poly-time LP solver.

ryan-nextmv 4y ago

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.

quickthrower2 4y ago
If so how can they claim this is in P time?
antiquark 4y ago
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.
- pxx 4y ago
  "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.

antiquark 4y ago

> 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?

stonemetal12 4y ago
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.
- blamestross 4y ago
  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.
  - stonemetal12 4y ago
    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.
    - ithinkso 4y ago
      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 http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf
- 4y ago

jdlyga 4y ago

Hard Cops: Chicago Streets Tuesdays at 9/8 Central

pierrebai 4y ago

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.

quickthrower2 4y ago
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!
- WorldMaker 4y ago
  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"?
  - danbruc 4y ago
    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.

deleted 4y ago

[deleted]