News for hackers. Stuff that matters.
Re:Magnus Carlsen to give up World Championship title by sweezyjeezy on Wednesday July 20, 2022 @08:15AM (#32164628)
Not sure if this was sarcasm, but that's like saying NP-hardness is no big deal because we only care about finite problems.
Re:Magnus Carlsen to give up World Championship title by adrianN on Wednesday July 20, 2022 @09:01AM (#32165162)
NP-hardness is indeed often not a big deal in practice because NP-hardness is a statement about asymptotic worst case complexity. In practice you have some finite size problems that are often of average difficulty, not of worst case difficulty. For example, we solve instances of SAT every day, some of them quite large. Even humans are able to solve many Sudoku puzzles, even though Sudoku is NP-hard.

If you hang with the right crowds (for example people into software correctness), PSPACE completeness is easy and you even solve undecidable problems every day.

Re:Magnus Carlsen to give up World Championship title by throwaway09223 on Wednesday July 20, 2022 @10:32AM (#32166290)
I solve the TSP every time I run errands.
Re:Magnus Carlsen to give up World Championship title by sabageti on Wednesday July 20, 2022 @11:05AM (#32166801)
How Sudoku is NP-Hard?
Re:Magnus Carlsen to give up World Championship title by CJefferson on Wednesday July 20, 2022 @12:32PM (#32168221)
If you generalise sudoku to a board with sides length, with subsquares with sides length n, then sudoku is no complete.
Re:Magnus Carlsen to give up World Championship title by jstanley on Wednesday July 20, 2022 @09:18AM (#32165368)
The reason chess is hard to solve is not because it's NP-hard (which it is not, being a constant-sized problem), it's because chess is a big problem.

It can simultaneously be true both that NP-hardness matters, and that constant-sized problems can be hard.

Re:Magnus Carlsen to give up World Championship title by sweezyjeezy on Wednesday July 20, 2022 @09:20AM (#32165390)
I never said chess was NP hard, it was an analogy. The equivalent would be some kind of chess on an NxN or Nx8 board I guess, I don't know how hard would be.
Re:Magnus Carlsen to give up World Championship title by dskloet on Wednesday July 20, 2022 @08:27AM (#32164762)
Chess on an 8x8 board is not NP-hard. That doesn't mean it's easy but invoking NP-hardness is kind of meaningless.
Re:Magnus Carlsen to give up World Championship title by bawolff on Wednesday July 20, 2022 @08:57AM (#32165108)
Like parent was saying - that is true of all problems in practise since the earth has finite resources. That doesn't make complexity classes a useless concept.

In other news, no point in needing pi, because perfect circles dont actually exist in the real world.

Re:Magnus Carlsen to give up World Championship title by pessimizer on Wednesday July 20, 2022 @11:44AM (#32167402)
I don't think people are trying to claim it's unimportant in general, to anyone, they're suggesting that it's completely unimportant in this conversation about how slow and boring championship chess matches are.
Re:Magnus Carlsen to give up World Championship title by sweezyjeezy on Wednesday July 20, 2022 @09:11AM (#32165289)
Yes and saying a problem is finite is also kind of meaningless. That narrows it down to everything except infinity. I also did not say that chess is NP-hard, it was an analogy.