4 ms·

Interesting tidbit, the Battleships puzzle is NP-complete (http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf http://www.mountainvistaso

Interesting tidbit, the Battleships puzzle is NP-complete (http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabil...) - there's no known solver algorithm that can do it in polynomial time, as the size of the puzzles / boards expand.

abetusk 2y ago
I think NP-Completness is the norm rather than the exception. Wikipedia has a list of NP-Complete problems [0]. [0] https://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles https://en.wikipedia.org/wiki/List_of_NP-complete_problems#G...
- thaumasiotes 2y ago
  > I think NP-Completeness is the norm rather than the exception. I don't think that's possible. Being NP-complete means a problem is as hard as any NP problem, and no harder. But there's not an upper limit to how difficult a problem can be. Note that the problem of determining whether two different regular expressions match the same set of strings is much harder than any NP-complete problem.
  - ianferrel 2y ago
    When you think about the class of things that humans consider to be "fun logic puzzles", NP-Completeness seems more common, since it encapsulates broadly the set of puzzles that require a certain amount of brute-force to find a solution to, and any reasonably entertaining human-solvable puzzle is easy to verify that something is in fact a solution.
  - abetusk 2y ago
    I think that's an unkind reading of my response. I was implicitly talking about decision problems or puzzle problems like the one in the OP. If you're talking about PSPACE complete problems or general Turing machine equivalence, I would extend the statement to include those as well. That is, PSPACE-completeness or general Turing machine equivalence are the norm rather than the exception. I'll also point out that a slight rephrasing of the question makes a statement about general computation into an NP-Complete problem. For example, instead of "Does this TM halt?" to "Is there some input for which this TM halts with finite tape length N in at most K steps?".
charlieyu1 2y ago
So that’s why so many puzzles seem to be impossible to solve except trial and error

abetusk 2y ago

I think NP-Completness is the norm rather than the exception. Wikipedia has a list of NP-Complete problems [0]. [0] https://en.wikipedia.org/wiki/List_of_NP-complete_problems#Games_and_puzzles https://en.wikipedia.org/wiki/List_of_NP-complete_problems#G...

thaumasiotes 2y ago
> I think NP-Completeness is the norm rather than the exception. I don't think that's possible. Being NP-complete means a problem is as hard as any NP problem, and no harder. But there's not an upper limit to how difficult a problem can be. Note that the problem of determining whether two different regular expressions match the same set of strings is much harder than any NP-complete problem.
- ianferrel 2y ago
  When you think about the class of things that humans consider to be "fun logic puzzles", NP-Completeness seems more common, since it encapsulates broadly the set of puzzles that require a certain amount of brute-force to find a solution to, and any reasonably entertaining human-solvable puzzle is easy to verify that something is in fact a solution.
- abetusk 2y ago
  I think that's an unkind reading of my response. I was implicitly talking about decision problems or puzzle problems like the one in the OP. If you're talking about PSPACE complete problems or general Turing machine equivalence, I would extend the statement to include those as well. That is, PSPACE-completeness or general Turing machine equivalence are the norm rather than the exception. I'll also point out that a slight rephrasing of the question makes a statement about general computation into an NP-Complete problem. For example, instead of "Does this TM halt?" to "Is there some input for which this TM halts with finite tape length N in at most K steps?".

charlieyu1 2y ago

So that’s why so many puzzles seem to be impossible to solve except trial and error