News for hackers. Stuff that matters.
Re:Solving NP-hard puzzles with the oldest trick in the book by Delk on Thursday October 14, 2021 @12:09PM (#28866211)
I didn't read the title that way. You can have a (heuristic) solver that finds solutions to some instances of an NP-hard problem in reasonable time. That's not the same as claiming to have an algorithm that, in the strict theoretical CS sense, would solve that problem (i.e. all instances of it) in polynomial time. The latter claim would be highly suspicious by default; the former need not be, as it doesn't imply anything extraordinary.

Quote from OP in another comment:

> I think a better way to phrase it is that we are writing a solver for a reasonable subset of inputs to an NP-hard problem.

Re:Solving NP-hard puzzles with the oldest trick in the book by master_yoda_1 on Thursday October 14, 2021 @01:08PM (#28866988)
Many expert spend life on approximation of np hard problem. For the name of holy God if you don’t understand something then please don’t trivialize it.
Re:Solving NP-hard puzzles with the oldest trick in the book by perl4ever on Thursday October 14, 2021 @10:58PM (#28873660)
Was the headline changed from "problem" to "puzzle"?
Re:Solving NP-hard puzzles with the oldest trick in the book by lostmsu on Friday October 15, 2021 @03:58PM (#28882402)
Is this even a NP-hard problem?
Re:Solving NP-hard puzzles with the oldest trick in the book by taintegral on Friday October 15, 2021 @07:08PM (#28884171)
I would really enjoy a proof that it is not!