Chaincamp

A minimal blog on the building blocks of ethereum & cryptographic primitives

27 Jul 2023

Chess, Sudoku and Complexity

Both Chess and Sudoku are interesting problems to consider in the context of computational complexity theory. They both have elements of deterministic and non-deterministic approaches when trying to solve them.

Chess:

  1. P vs NP:

    • Chess is not a decision problem, so it doesn’t exactly fit into the categories of P or NP.
    • However, the problem of determining whether a given position is a winning position can be seen as a decision problem. This problem, known as the Generalized Chess problem, is EXPTIME-complete. This means it’s believed to be more complex than any problem in P or NP, requiring exponential time to solve in the worst case.

  2. PSPACE vs NPSPACE:

    • Chess, as a decision problem, is in PSPACE. This is because you can theoretically solve the problem using a polynomial amount of space by exploring all possible games.
    • Due to Savitch’s theorem, which states that PSPACE = NPSPACE, Chess as a decision problem is also in NPSPACE.

Sudoku:

  1. P vs NP:

    • Sudoku is a decision problem and belongs to the class of NP problems. The problem of determining whether a Sudoku puzzle has a solution can be solved in non-deterministic polynomial time.
    • Specifically, the decision problem version of Sudoku is NP-complete. This means it is among the hardest problems in NP, in the sense that a solution to this problem can be used to solve all other problems in NP.

  2. PSPACE vs NPSPACE:

    • Sudoku, as a decision problem, also belongs to PSPACE. Even though it’s an NP-complete problem, all problems in NP are also in PSPACE.
    • Due to Savitch’s theorem, Sudoku as a decision problem is also in NPSPACE.

Sources:

  1. “Complexity of Games and Puzzles” - https://larc.unt.edu/ian/research/cs/
  2. “The Complexity of Sudoku” by Oded Goldreich - https://www.wisdom.weizmann.ac.il/~oded/COL/sudoku.pdf
  3. “Computational Complexity: A Modern Approach” by Sanjeev Arora and Boaz Barak - http://www.cs.princeton.edu/theory/complexity/
  4. “Introduction to the Theory of Computation” by Michael Sipser
  5. “Games, Puzzles, and Computation” by Robert Hearn and Erik Demaine.