3 ms·
Could you be more specific about the fraud? Optimizing your code to use appropriate data structures, and using state reduction to remove symmetries and duplicat
by gwern 5y ago
Could you be more specific about the fraud? Optimizing your code to use appropriate data structures, and using state reduction to remove symmetries and duplicate states seems like a perfectly cromulent way of reducing a problem to its true core, which may be small enough to bruteforce.
- master_yoda_1 5y agoClaiming to solve np hard problem is a fraud. Just put optimizing code in title.
- throwaway81523 5y ago> Claiming to solve np hard problem is a fraud. Claiming to solve an np hard problem in polynomial time on all inputs would be either a fraud or a breakthrough. This is not such a claim. The algorithm is organized to perform well on many but not all inputs--its worst case is exponential time and it doesn't pretend to be otherwise. If you play chess against a chess engine like Stockfish, the exact same thing is going on, and in fact the algorithms involved are closely related to the one in the article.