4 ms·

I request the moderator of hn to please flag this post. This fraud is claiming to solve np hard problem in title and some jokers at hn make it to the front page

I request the moderator of hn to please flag this post. This fraud is claiming to solve np hard problem in title and some jokers at hn make it to the front page of hn

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 ago
  Claiming 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.
Delk 5y ago
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.
- master_yoda_1 5y ago
  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.
  - perl4ever 5y ago
    Was the headline changed from "problem" to "puzzle"?
- lostmsu 5y ago
  Is this even a NP-hard problem?
  - taintegral 5y ago
    I would really enjoy a proof that it is not!
kbelder 5y ago
People solve specific np-hard problems all the time, every day. They just don't solve THE np-hard problem.
perl4ever 5y ago
I'd suggest that maybe "puzzle" has a slightly different connotation than "problem". I think a "puzzle" is a concrete instance of a more formal and abstract "problem". So I don't think claiming to solve an instance (or many!) of a problem is inappropriate.

I request the moderator of hn to please flag this post. This fraud is claiming to solve np hard problem in title and some jokers at hn make it to the front page of hn

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 ago
Claiming 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.

Delk 5y ago

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.

master_yoda_1 5y ago
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.
- perl4ever 5y ago
  Was the headline changed from "problem" to "puzzle"?
lostmsu 5y ago
Is this even a NP-hard problem?
- taintegral 5y ago
  I would really enjoy a proof that it is not!

kbelder 5y ago

People solve specific np-hard problems all the time, every day. They just don't solve THE np-hard problem.

perl4ever 5y ago

I'd suggest that maybe "puzzle" has a slightly different connotation than "problem". I think a "puzzle" is a concrete instance of a more formal and abstract "problem". So I don't think claiming to solve an instance (or many!) of a problem is inappropriate.