[scscsc]

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:.

[jvanderbot]

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.

[blt]

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

[jvanderbot]

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.

[amelius]

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

[jvanderbot]

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

[cs702]

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

[nyrikki]

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

[Davidzheng]

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

[thomasahle]

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.