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

Re:“P = NP” Polynomial-Sized LP Models for Hard Cops by zelos on Thursday January 26, 2023 @08:08AM (#34531171)

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?

[ Parent | on HN ]

Re:“P = NP” Polynomial-Sized LP Models for Hard Cops by throw_pm23 on Thursday January 26, 2023 @08:30AM (#34531381)

If the claim were true that the solution is always integer, then one could use a poly-time LP solver.

[ Parent | on HN ]

Re:“P = NP” Polynomial-Sized LP Models for Hard Cops by coliveira on Thursday January 26, 2023 @08:26AM (#34531341)

But this leads to an exponential time algorithm.

[ Parent | on HN ]