News for hackers. Stuff that matters.
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.
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.