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].
Table of Contents
1 Introduction
1.1 Overview
2 The Basics
2.1 What is Minesweeper?
2.2 Complexity theory: complexity classes
2.2.1 The complexity class NP
2.2.2 The complexity class P
2.2.3 The complexity class co-NP
2.2.4 Possible relations among the complexity classes P, NP and co-NP
2.2.5 The hierarchy of complexity classes
2.3 Complexity theory: problem instances
2.3.1 Decision problems as formal languages
2.3.2 What does decidability mean?
2.3.2.1 A simple example for a decidable language
2.3.2.2 How to prove the language ADF A to be decidable
2.3.3 What does reducibility mean?
2.3.4 What does NP-hard mean?
2.3.5 What is completeness?
2.3.5.1 How to show that a problem is NP-complete
2.3.5.2 How to show that a problem is co-NP-complete
2.3.6 Satisfiability SAT
2.3.7 Unsatisfiability UNSAT
2.4 Summary
3 “Minesweeper is NP-complete”
3.1 Introducing the paper
3.1.1 Minesweeper Consistency Problem MCP
3.1.2 MCP is in NP
3.2 Reduction from SAT
3.2.1 Introduction to the Reduction
3.3 Boolean Circuits in Minesweeper
3.4 Composing circuits with basic building blocks in Minesweeper syntax
3.4.1 An AND-gate in Minesweeper
3.4.2 An OR-gate in Minesweeper
3.5 Summary
4 “Minesweeper May Not Be NP-complete But Is Hard Nonetheless”
4.1 Introducing the Paper
4.2 Minesweeper Inference Problem MIP
4.2.1 MIP search
4.2.2 MIP decision
4.3 Minesweeper Inference MIP is in co-NP
4.3.1 Reduction from UNSAT
4.3.1.1 Converting the Input: F ↔ F’
4.3.1.2 Construction of the Boolean circuit
4.3.1.3 Construction of the board
4.3.2 Correctness of the reduction
4.3.3 Reduction from UNSAT explained with a concrete example
4.4 Summary
5 Conclusion
5.1 Results
5.2 Kaye: “Minesweeper is NP-hard”
5.2.1 What if Kaye was right?
5.3 Scott: “Minesweeper may not be NP-complete but is hard nonetheless”
5.4 Conclusion
Research Objectives and Themes
This thesis examines the computational complexity of the video game Minesweeper, specifically analyzing whether it belongs to complexity classes such as NP-complete or co-NP-complete, through a critical review of existing academic research.
- Theoretical foundations of computational complexity classes (P, NP, co-NP).
- Analysis of Richard Kaye's proof regarding Minesweeper's NP-completeness.
- Evaluation of Allan Scott's alternative interpretation of the game's hardness.
- Formal reduction of Boolean Satisfiability (SAT) and Unsatisfiability (UNSAT) to Minesweeper configurations.
- The role of the Minesweeper Consistency Problem and Minesweeper Inference Problem in game strategy.
Excerpt from the Thesis
3.4.1 An AND-gate in Minesweeper
As known, a logical AND has the following truth table (fig. 3.8). Obviously, the only way to make sure that the output is TRUE is to assign this very value to both of the inputs.
An AND-gate can be constructed with the basic Minesweeper Boolean circuits we have just learned. (See figure 3.9).
This example is rather complex: We have two input wires U and V and one output T. The red marked area, especially the square containing the value 4 in between S and R in figure 3.10 is where both inputs are brought together and the output T is initialized. The depicted signals S and R in this square are called “internal wires” and are used for ensuring consitency [1], [17]. They use the fields a1, a2, a3, b1, b2, b3 to make sure the output is logically correct. At the end, the splitter produces one single output T.
Summary of Chapters
1 Introduction: Provides an overview of the thesis objectives, the study of complexity theory, and the key papers by R. Kaye and A. Scott that form the foundation of the work.
2 The Basics: Defines essential concepts including complexity classes (P, NP, co-NP), decidability, reducibility, completeness, and specific problems like SAT and UNSAT.
3 “Minesweeper is NP-complete”: Explores Kaye's proof, the Minesweeper Consistency Problem (MCP), and the construction of Boolean circuits using Minesweeper syntax (NOT, AND, OR gates).
4 “Minesweeper May Not Be NP-complete But Is Hard Nonetheless”: Discusses Scott's critique, introducing the Minesweeper Inference Problem (MIP) and proving its co-NP-completeness via reduction from UNSAT.
5 Conclusion: Summarizes the results, reflecting on the potential implications of a P=NP solution and the broader significance of Minesweeper in theoretical computer science.
Keywords
Minesweeper, Computational Complexity, NP-complete, co-NP-complete, SAT, UNSAT, Minesweeper Consistency Problem, MCP, Minesweeper Inference Problem, MIP, Boolean circuits, Logic gates, Decidability, Polynomial time, Theoretical computer science.
Frequently Asked Questions
What is the primary focus of this thesis?
The work investigates the computational complexity of the game Minesweeper, specifically evaluating whether the game is NP-complete or presents other forms of hardness.
What are the central themes covered?
The core themes include formal complexity theory, the reduction of Boolean logic circuits to Minesweeper grid configurations, and a comparative analysis of the consistency versus inference versions of the game.
What is the main research question or goal?
The goal is to determine the complexity classification of Minesweeper by analyzing two major perspectives: Kaye's argument for NP-hardness and Scott's argument for co-NP-completeness regarding game inference.
Which scientific methods are utilized?
The research relies on literature review and theoretical analysis, specifically using polynomial-time reductions to demonstrate that Boolean satisfiability problems can be mapped onto Minesweeper boards.
What topics are discussed in the main body?
The main body covers the definition of complexity classes, the translation of logical gates (AND, OR, NOT) into Minesweeper board layouts, and detailed proofs regarding consistency and inference.
Which keywords characterize this work?
The key terms include NP-complete, co-NP, Minesweeper, Consistency Problem, Inference Problem, Boolean logic, and complexity theory.
How does the game strategy relate to the Minesweeper Inference Problem (MIP)?
The MIP defines whether a player can definitively determine the state of a square based on existing board information; solving this is necessary for optimal, non-speculative play.
What is the significance of the "red area" in the AND-gate construction?
The red area represents the junction where two input signals are compared. It is critical for ensuring that the Minesweeper configuration remains consistent with the intended logical truth table.
Why does the thesis mention the "Clay Mathematics Institute"?
The author highlights the Millennium Prize Problems, noting that the P vs. NP question is one of the most significant open challenges in mathematics, which the complexity of Minesweeper touches upon.
- Citar trabajo
- Polina Yakovleva (Autor), 2013, Minesweeper. Varianten und Komplexität, Múnich, GRIN Verlag, https://www.grin.com/document/264848
