News for hackers. Stuff that matters.

A comment on “P = NP” Polynomial-Sized LP Models for Hard Cops. Parent comment

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.

[ Parent | on HN ]
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.
[ Parent | on HN ]