Computational complexity of games

10 entries

Sort by date added | title

• Flat origami is Turing Complete
  • Published in 2023
  • Added on 2023-09-29
• Hyperbolic Minesweeper is in P
  • Published in 2020
  • Added on 2023-08-14
• The distance of a permutation from a subgroup of \(S_n\)
  • Published in 2005
  • Added on 2020-04-30
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
  • Published in 2001
  • Added on 2018-01-23
• Markets are efficient if and only if P = NP
  • Published in 2011
  • Added on 2013-02-11
• Mastermind is NP-Complete
  • Published in 2005
  • Added on 2012-09-02
• Computer analysis of Sprouts with nimbers
  • Published in 2010
  • Added on 2012-04-21
• Gaming is a hard job, but someone has to do it!
  • Published in 2012
  • Added on 2012-01-27
• The hardness of the Lemmings game, or Oh no, more NP-completeness proofs
  • Published in 2004
  • Added on 2012-01-27
• Tetris is Hard, Even to Approximate
  • Published in 2008
  • Added on 2011-11-23