4 ms·
Not all continuous optimization algorithms can handle arbitrary equality constraints, especially if they effectively make the optimization domain discrete. You
by yorwba 9y ago
Not all continuous optimization algorithms can handle arbitrary equality constraints, especially if they effectively make the optimization domain discrete. You might be able to do an encoding of NP-complete problems that is purely continuous, but if I read the LIPO paper correctly, there is a known exponential lower bound for their problem, so that would just make the NP-complete problem harder.
Instead, the algorithm promises to actually match that lower bound, while always being at least as good as random search, and offering exponentially large improvements in certain cases. Not exactly the kind of claim that has implications for P =? NP.