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