Hacker News Reader

Comment by scscsc | Hacker News Reader

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

View on HN

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.

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

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

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.

Reply on news.ycombinator.com