6 ms·
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:.
by scscsc 3y ago
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:.
- cs702 3y agoThank you for that. I needed the laugh :-)
- Davidzheng 3y agoProbably soon AI will be able to find improvements to most of them? Like using AI to do search in algorithm space
- thomasahle 3y agoFor 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.
- jvanderbot 3y agoAI + 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.
- amelius 3y agoEven solving large linear systems would already be amazing. But a SAT solver would be nice too :)
- jvanderbot 3y agoI misunderstand your comment. We have those solvers. I'm suggesting AI would plug into existing solvers. This is a ripe area for research.
- blt 3y agoIt is happening. There are papers on deep learning to improve the variable choice in branch-and-bound, etc
- jvanderbot 3y agoYeah 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.
- nyrikki 3y agoFor 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 https://web.stanford.edu/class/cs354/scribe/lecture17.pdf