Re:Solving NP-hard puzzles with the oldest trick in the book
by gwern on Thursday October 14, 2021 @11:52AM
(#28865984)
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.
[ Parent
| on HN ]
Re:Solving NP-hard puzzles with the oldest trick in the book
by master_yoda_1 on Thursday October 14, 2021 @01:06PM
(#28866959)
Claiming to solve np hard problem is a fraud. Just put optimizing code in title.
Re:Solving NP-hard puzzles with the oldest trick in the book
by throwaway81523 on Thursday October 14, 2021 @02:08PM
(#28867794)
> 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.