Hacker News Reader

Comment by amelius | Hacker News Reader

Is someone keeping a list of classical algorithms or NP complete problems that are now better performed using deep learning?

View on HN

For your convenience, here is the list of NP-complete problems where "AI" works better than the state of the art in the worst case:.

Thank you for that. I needed the laugh :-)

Probably soon AI will be able to find improvements to most of them? Like using AI to do search in algorithm space

For all we know, some of the current best (still exponential) algorthms were guided by AI. If a mathematician solves a problem using mathematica, they don't usually write in the paper what tools they used.

AI + classical algorithms is my sweet daydream. Trained heuristics (even better domain specific ones), deployed for classical A*, ILP families, focal search, etc etc.

That is going to be really amazing.

Even solving large linear systems would already be amazing. But a SAT solver would be nice too :)

I misunderstand your comment. We have those solvers. I'm suggesting AI would plug into existing solvers. This is a ripe area for research.

It is happening. There are papers on deep learning to improve the variable choice in branch-and-bound, etc

Yeah my first exposure was from Marco Pavone's lab, on ML heuristics for MICP in the context of a cubical tumbling robot, IIRC. Really cool stuff.

For those of you who didn't get the joke here.

(S)ETH is a bit of a bummer if you only consider the dominate term in big-O, for the general case.

https://web.stanford.edu/class/cs354/scribe/lecture17.pdf

From my understanding this is very much still active research, without any clear wins deployed in production settings.

Reply on news.ycombinator.com