Minesweeper may not be NP-complete but is hard nonetheless

DOI10.1007/s00283-011-9256-xzbMath1248.68223OpenAlexW2126010852WikidataQ63285632 ScholiaQ63285632MaRDI QIDQ660171

Ulrike Stege, Allan Scott, Iris van Rooij

Publication date: 29 January 2012

Published in: The Mathematical Intelligencer (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00283-011-9256-x

zbMATH Keywords

computational complexityNP-completenessMinesweeper

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Covert computation in self-assembled circuits ⋮ \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\) ⋮ Unnamed Item ⋮ Knowledge-based programs as succinct policies for partially observable domains ⋮ LaserTank is NP-Complete ⋮ Rikudo is NP-complete

This page was built for publication: Minesweeper may not be NP-complete but is hard nonetheless