[HN Gopher] "P = NP" Polynomial-Sized LP Models for Hard Cops
___________________________________________________________________
"P = NP" Polynomial-Sized LP Models for Hard Cops
Author : mikk14
Score : 47 points
Date : 2023-01-26 08:21 UTC (14 hours ago)
(HTM) web link (tsplp.research.uconn.edu)
(TXT) w3m dump (tsplp.research.uconn.edu)
| ryan-nextmv wrote:
| 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.
| antiquark wrote:
| 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.
| danbruc wrote:
| 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 wrote:
| What if you use 0.0000000000000001 and 1-that?
| adrianN wrote:
| Then you don't get the optimal integer solution, which can
| (in general) be arbitrarily far away from the optimal real
| solution.
| zelos wrote:
| 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 wrote:
| But this leads to an exponential time algorithm.
| throw_pm23 wrote:
| If the claim were true that the solution is always integer,
| then one could use a poly-time LP solver.
| missingdays wrote:
| The challenge has been up for a year now. Is the counter
| example too hard to find and not worth $10,000?
| danbruc wrote:
| 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 n6 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.
| onos wrote:
| 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".
| TimPC wrote:
| 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 wrote:
| 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.
| danbruc wrote:
| 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.
| pierrebai wrote:
| 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.
| gweinberg wrote:
| 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.
| quickthrower2 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| antiquark wrote:
| > 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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
| nwallin wrote:
| 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.
| [deleted]
| tempodox wrote:
| "Hard COPs", not "Hard Cops". Is this HN's auto-capitalizing?
| moss2 wrote:
| Maybe the police are aroused by computational problems
| ghordynski wrote:
| 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?
| jdlyga wrote:
| Hard Cops: Chicago Streets
|
| Tuesdays at 9/8 Central
___________________________________________________________________
(page generated 2023-01-26 23:02 UTC)