Before elaborating on the complexity of Minesweeper, the basic ideas of complexity theory and the rules of the game shall be introduced. Both subjects should be internalized in order to understand the contents of this bachelor thesis. The basics are learned from: Introduction to the Theory of Complexity by M. Sipser [20], H. Vollmer Skript zur Vorlesung Komplexität von
Algorithmen [21] and S. Arora and B. Barak Computational Complexity: A Modern Approach [19].
Further, this bachelor thesis will be based upon the main results of these two papers:
Minesweeper is NP complete by R. Kaye [1],
Minesweeper May Not Be NP-Complete but Is Hard Nonetheless by A. Scott [2].
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Overview
- The Basics
- What is Minesweeper?
- Complexity theory: complexity classes
- The complexity class NP
- The complexity class P
- The complexity class co-NP
- Possible relations among the complexity classes P, NP and co-NP
- The hierarchy of complexity classes
- Complexity theory: problem instances
- Decision problems as formal languages
- What does decidability mean?
- A simple example for a decidable language
- How to prove the language ADF A to be decidable
- What does reducibility mean?
- What does NP-hard mean?
- What is completeness?
- How to show that a problem is NP-complete
- How to show that a problem is co-NP-complete
- Satisfiability SAT
- Unsatisfiability UNSAT
- Summary
- “Minesweeper is NP-complete”
- Introducing the paper
- Minesweeper Consistency Problem MCP
- MCP is in NP
- Reduction from SAT
- Introduction to the Reduction
- Boolean Circuits in Minesweeper
- Composing circuits with basic building blocks in Minesweeper syntax
- An AND-gate in Minesweeper
- An OR-gate in Minesweeper
- Summary
- Introducing the paper
- “Minesweeper May Not Be NP-complete But Is Hard Nonetheless”
- Introducing the Paper
- Minesweeper Inference Problem MIP
- MIP search
- MIP decision
- Minesweeper Inference MIP is in co-NP
- Reduction from UNSAT
- Converting the Input: F ↔ F’
- Construction of the Boolean circuit
- Construction of the board
- Correctness of the reduction
- Reduction from UNSAT explained with a concrete example
- Reduction from UNSAT
- Summary
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This bachelor thesis explores the computational complexity of the popular game Minesweeper. The main objective is to analyze the game from a complexity theory perspective, investigating its relationship with prominent complexity classes such as NP and co-NP. The thesis aims to demystify the notion of NP-completeness in the context of Minesweeper, highlighting the work of Kaye and Scott in this field. The key themes investigated include:- The Minesweeper Consistency Problem (MCP) and its NP-hardness
- The Minesweeper Inference Problem (MIP) and its co-NP-completeness
- The implications of these findings for the P vs. NP problem and the NP vs. co-NP problem
- The practical relevance of complexity theory in game design and real-world applications
Zusammenfassung der Kapitel (Chapter Summaries)
- Chapter 2 introduces the game Minesweeper and fundamental concepts from complexity theory, including complexity classes, decidability, reducibility, completeness, and the problems SAT and UNSAT.
- Chapter 3 examines Kaye's work, which claimed that Minesweeper is NP-complete. This chapter explains Kaye's Minesweeper Consistency Problem and its NP-hardness proof, demonstrating how Boolean circuits can be represented in Minesweeper.
- Chapter 4 delves into Scott's paper, which refutes Kaye's claim. It introduces the Minesweeper Inference Problem and proves its co-NP-completeness. This chapter also provides a detailed explanation of the reduction from UNSAT to MIP.
Schlüsselwörter (Keywords)
This bachelor thesis investigates the complexity of the game Minesweeper, focusing on its relationship with key complexity classes. The main concepts explored include NP-completeness, co-NP-completeness, Minesweeper Consistency Problem (MCP), Minesweeper Inference Problem (MIP), Boolean circuits, reduction, and the P vs. NP problem.Frequently Asked Questions
Is Minesweeper NP-complete?
The paper by Richard Kaye argues that Minesweeper is NP-complete, while a later paper by Scott suggests it may not be, but remains "hard nonetheless."
What is the Minesweeper Consistency Problem (MCP)?
MCP is a decision problem used to prove NP-hardness by demonstrating that Minesweeper can represent Boolean circuits.
What is the Minesweeper Inference Problem (MIP)?
MIP is a problem introduced by Scott that is proven to be co-NP-complete, focusing on whether a certain square must contain a mine.
How can Minesweeper represent Boolean gates?
The thesis shows how specific board configurations can function as AND-gates and OR-gates within Minesweeper syntax.
What complexity classes are discussed in the thesis?
The work discusses the hierarchy and relations between complexity classes P, NP, and co-NP.
- Quote paper
- Polina Yakovleva (Author), 2013, Minesweeper. Varianten und Komplexität, Munich, GRIN Verlag, https://www.grin.com/document/264848
