Re:“P = NP” Polynomial-Sized LP Models for Hard Cops
by ryan-nextmv on Thursday January 26, 2023 @09:58AM
(#34532395)
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.
[ Parent
| on HN ]
Re:“P = NP” Polynomial-Sized LP Models for Hard Cops
by antiquark on Thursday January 26, 2023 @10:57AM
(#34533369)
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.
Re:“P = NP” Polynomial-Sized LP Models for Hard Cops
by pxx on Friday January 27, 2023 @10:07AM
(#34546848)
"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.
Re:“P = NP” Polynomial-Sized LP Models for Hard Cops
by quickthrower2 on Friday January 27, 2023 @01:42AM
(#34543317)
If so how can they claim this is in P time?