No article text was recorded for this version.
computational complexity of logic puzzles
Version 1 of 116 papers32 conceptsfrozen 2026-10-04
Papers in this version
- Blog: A tractability gap beyond nim-sums: It's hard to tell whether a bunch of superstars are losers
- Blog: Tetris is NP-hard even with O(1) Rows or Columns
- Blog: A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem
- Blog: Tatamibari is NP-complete
- Blog: NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
- Blog: How to Solve the Torus Puzzle
- Blog: Learning Minesweeper with Multinational Learning
- Blog: Trainyard is NP-Hard
- Blog: Computational Intractability and Solvability for the Birds of a Feather Game
- Blog: The computational complexity of Angry Birds
- Blog: The Computational Complexity of Angry Birds (Extended Abstract)
- Blog: The Computational Complexity of Angry Birds and Similar Physics-Simulation Games
- Blog: PSPACE-completeness of Pulling Blocks to Reach a Goal
- Blog: Predicting Unsolvable Deals in the Birds of a Feather Solitaire Game
- Blog: Bejeweled, Candy Crush and other match-three games are (NP-)hard
- Blog: This Game Is Not Going To Analyze Itself
History & citation
Current · Permanent link
Cite this direction
Latest version (a living page):
@misc{lacuna_computational_complexity_of_logic_puzzle_74fafc3c,
title = {computational complexity of logic puzzles},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-logic-puzzles/rdr_74fafc3c0d534a5ea646781bc2800cc2},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}This exact version (version 1, frozen text):
@misc{lacuna_computational_complexity_of_logic_puzzle_74fafc3c_v1,
title = {computational complexity of logic puzzles},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-logic-puzzles/rdr_74fafc3c0d534a5ea646781bc2800cc2/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}