Excerpt
Contents
Declaration of Authorship
Acknowledgements
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 ADFA 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
Bibliography
Acknowledgements
Above all, I would particularly like to express my gratitude to Patrick Fam for his support and patience.
I appreciate the feedback offered by Roberto Henschel.
Further I thank Prof. Dr. Heribert Vollmer for giving advice and encouragement.
Chapter 1 Introduction
1.1 Overview
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. Sipser20, H. Vollmer Skript zur Vorlesung Komplexität von Algorithmen21 and S. Arora and B. Barak Computational Complexity: A Modern Approach19.
Further, this bachelor thesis will be based upon the main results of these two papers:
Minesweeper is NP complete by R. Kaye1, Minesweeper May Not Be NP-Complete but Is Hard Nonetheless by A. Scott2.
Chapter 2 The Basics
2.1 What is Minesweeper?
Minesweeper is a single-player game which comes as a standard feature of Microsoft Windows. It was released in the year 1992 as a part of Windows 3.1.18. The initial state of the game finds the player faced with a (n × m)-board full of covered squares. While the current configuration of each square is initially unknown to the player, he is aware (if familiar with the rules of the game) that a square can either contain a mine or a digit between the values 0 and 8. The goal of the game and ultimately its challenge is to discover every hidden mine without actually revealing it. Therefore, no square containing a mine is allowed to be opened (clicked upon). Otherwise the player will figuratively “step on a mine” and lose the game. For each square the player has the same two options: He can either open the square or mark it with a right mouse click. Marking squares means that the player is of the opinion that a mine may be hidden at this particular spot. The flag thereby set acts as a reminder but has no actual function. If the player clicks on a square which is free of mines, the square opened will display a number. This number is an indicator of neighboring squares that contain mines. Depending on a certain constellation, the player may eventually be unable to conclude the correct content of a square. He therefore has to speculate and is forced to open a square, the content of which he is unsure about.
Assuming that the number displayed has the value 3. This means that three adjacent squares each contain a mine and the remaining five do not. Of course, if the square is placed at the edge of the board, the number of the remaining “safe” squares will decrease. Figure 2.1 shows an example for n = m = 9 and k = 10. The variable k stands for the number of mines placed on the board. Here, the player has just lost the game after having marked two mines correctly and then stumbling upon the crucial third mine. Each time the flag is set the mine-counter k is reduced by the value of 1. This is shown by the number down to the right in figure 2.1. It has the value k = 8, since two fields have already been marked by the player.
illustration not visible in this excerpt
Figure 2.1: Introducing the board -a typical Minesweeper board constellation.
By clicking on an empty sector, every neighboring field which does not contain a mine and has the value 0 will be revealed automatically until it is enframed by digits. (See fig- ure 2.2). This functions merely as a simplification for the player. The area of connected, uncovered squares with no mines around them is defined as the whitespace component by de Bondt4.
illustration not visible in this excerpt
Figure 2.2: By clicking on the empty square (marked with the red question mark) every other neighboring empty sector which has the value 0 is revealed until a digit appears.
2.2 Complexity theory: complexity classes
After having examined the rules of Minesweeper, it is important to now understand the complexity theory behind the game. In the following section, I shall first explain certain complexity classes which are of interest for this work.
2.2.1 The complexity class NP
The abbreviation NP stands for non-deterministic polynomial time and refers to one of the most basic and important complexity classes in complexity theory.
Definition 1.
Polynomial time is the amount of time needed to solve an algorithm. The number of steps is bounded by O(nk), where n is the size of the input and the exponent k is a nonnegative integer15.
NP contains problems which have efficiently verifiable solutions. This means that even without knowing an efficient, polynomial-time way to actually solve a problem, it is still possible to check whether a provided solution is accepted. The provided solution is also called certificate. The term verifier is also of great importance for this complexity class. It is a synonym for the corresponding Turing machine (TM) M, since this machine verifies the certificate to be a correct solution for the current NP-problem19.
Definition 2.
NP is the set of problems which have polynomial-time certificates. Formally speaking, it means: A language L ⊆ {0, 1}∗. Therefore, running M as a function of L (represented by M (x, u)) with the result M (x, u) = 0 would mean that the algorithm or solution provided would not be a correct one - it would not satisfy M (x, u). On the contrary, M (x, u) = 1 is the case which is of specific interest for the context.
L lies in NP, if both a polynomial p : N → N and a polynomial-time TM M exist so that for every [Abbildung in dieser Leseprobe nicht enthalten] so that M (x, u) = 1. This is to be understood as follows: The input x belongs to the language L iff, there exists a u which is a word over the alphabet {0, 1} and has at most the size of the polynomial p applied to the size ot the input [Abbildung in dieser Leseprobe nicht enthalten] satisfy M (x, u), then u is called a certificate for x.
2.2.2 The complexity class P
Another fundamental complexity class is called P. P simply stands for (deterministic) polynomial time and includes all problems that can be solved in polynomial time by a deterministic Turing machine.
Definition 3.
P is the set of problems which can be solved in polynomial time by a Turing machine. A language L is in P iff there exists a deterministic Turing machine M so that L, represented by M (x), in polynomial time outputs 1 for all x in L and outputs 0 for all x not in L. Here, x ∈ {0, 1}∗.
2.2.3 The complexity class co-NP
Now that we are of knowledge about the complexity class NP, it is time to introduce another class which is connected to NP, namely co-NP. Co-NP means complement-NP and contains the problems that are complements of those in NP. Whether co-NP is in fact different from NP is not known however. “Problems for which ‘No’ answers can be verified in polynomial time are said to belong to co-NP. [...] In general, for any decision problem Q in NP there exists a complement problem co-Q in co-NP, which has the answers ‘Yes’ and ‘No’ reversed”2.
2.2.4 Possible relations among the complexity classes P, NP and co- NP
There are three scenarios possible: P = NP and NP = co-NP, or P = NP and NP = co-NP, or P = NP = co-NP.
illustration not visible in this excerpt
Figure 2.3: Possible relations among the classes P, NP and co-NP.
2.2.5 The hierarchy of complexity classes
To provide a better understanding and to give an overview, figure 2.4 presents the hierarchy of the complexity classes discussed in this section.
illustration not visible in this excerpt
Figure 2.4: Representation of the complexity hierarchy of the classes P, NP and co-NP.
2.3 Complexity theory: problem instances
After having learned of the relations of complexity classes, it is essential for this work to regard some computational problems, their characteristics and possible operations.
2.3.1 Decision problems as formal languages
A decision problem can be considered as a formal language. The members of a certain language are known to be instances of decision problems whose output is YES. Nonmembers are those whose output is NO.
2.3.2 What does decidability mean?
Decidability is an attribute of languages. It means that there are certain languages in computational theory which can be handled by a Turing machine (which is to be adjusted). This Turing machine will eventually halt on the input. It will either accept or reject the language.
2.3.2.1 A simple example for a decidable language
A simple example for a decidable language is:
illustration not visible in this excerpt
Here, B is a deterministic finite automaton and w is the language-input. There is no difference in showing whether the deterministic finite automaton B accepts the input w or whether < B,w > is a member of the language [Abbildung in dieser Leseprobe nicht enthalten]. Briefly speaking, it is the same to show that a language is decidable or to prove the appropriate computational problem to be decidable.
2.3.2.2 How to prove the language [Abbildung in dieser Leseprobe nicht enthalten] to be decidable
A Turing machine M which decides the language [Abbildung in dieser Leseprobe nicht enthalten] has to be introduced. The input is a deterministic finite automaton B and a string w.
1. Run the automaton B with the input w.
2. If the automaton B enters an accepting finite state, accept the input. If it enters a rejecting finite state, reject it.
This abstract proof may need some explanation. The automaton B is represented by Q, Σ, δ, q0, and F :
- Q describes a finite set of states the automaton can enter.
- Σ is called alphabet and includes a finite set of inputs.
- δ is a transition function.
- q0 is called the start state of the automaton. One has q0 ∈ Q.
- F is a set of the accept states of the automaton.
The Turing machine M receives the input of B and accepts it only if the input is a correct representation of B and of the string w. After the simulation process, M finally accepts the input, if B enters and stays in an accepting state. Otherwise, M rejects.
2.3.3 What does reducibility mean?
Reducibility helps to distinguish and compare the difficulty levels of complexity prob- lems. In a few words, reducing is the process of transforming a certain problem A into another one B in such a way that the solution provided to B can be re-transformed to be an adequate solution for the problem A. One says that A is not harder than B and therefore: (A ≤ B).
Definition 4.
One has A ⊂ Σ∗, B ⊂ Δ∗, both Σ Δ are alphabets while A and B are languages. A is reducible to B, if there exists a function [Abbildung in dieser Leseprobe nicht enthalten] with the following properties: A Turing machine M , which runs in polynomial time getting an input x ∈ Σ∗ will produce an output f (x) ∈ Δ∗, so that [Abbildung in dieser Leseprobe nicht enthalten] one has [Abbildung in dieser Leseprobe nicht enthalten]
2.3.4 What does NP-hard mean?
“A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself”20. A problem is polynomial-time reducible to another problem, if the reduction is computable by a deterministic Turing machine in polynomial time.
Definition 5.
A language B is NP-hard, if ∀ A ∈ NP via a deterministic polynomial-time reduction one has (A ≤ B).
2.3.5 What is completeness?
In computational theory, a problem is complete, if it is among the hardest, most expressive problems in the complexity class. As mentioned in section 2.3.3, it is said that A is not harder than B and therefore (A ≤ B). So if there exists an algorithm which solves B, A can be solved as well. Consequently, B is one of the hardest problems in NP, if every other problem A ∈ N P is not harder than B.
Definition 6.
A language B is NP-complete, if B is NP-hard and B ∈ NP.
2.3.5.1 How to show that a problem is NP-complete
Let us assume that the problem B is NP-complete and C ∈ N P . If (B ≤ C), then C would be NP-complete too.
Is[Abbildung in dieser Leseprobe nicht enthalten]
Proof.
Let A ∈ N P . Since B is NP-complete, one has (A ≤ B). Because (B ≤ C) and the reduction ≤ is known to be transitive, it follows that A ≤ C.
2.3.5.2 How to show that a problem is co-NP-complete
A problem B is said to be co-NP-complete, if
1. B is a member of co-NP and
2. B is co-NP-hard.
Similarly to NP-completeness, if it could be shown that any co-NP-complete problem is solvable in polynomial time, then all other problems in co-NP would be, too. This would therefore imply P = NP2.
2.3.6 Satisfiability SAT
Now that the basic complexity classes and their relations are familiar, I shall go on by introducing other instances which are of interest for my thesis. For instance, the complexity problem SAT. This abbreviation refers to the satisfiability problem of Boolean expressions. The satisfiability problem is to analyze whether a Boolean formula is satisfiable, whereby the certificate is the assignment making the formula evaluate to 1. SAT is known to be NP-complete Cook-Levin theorem).
Definition 7.
SAT = [Abbildung in dieser Leseprobe nicht enthalten]is a Boolean formula in CNF which is satisfiable}21.
A Boolean formula is satisfiable, if some assignment of 0s and 1s to the variables makes the formula evaluate to 1.
For instance, the Boolean formula[Abbildung in dieser Leseprobe nicht enthalten] is satisfiable with the assignment y=1,z=020.
2.3.7 Unsatisfiability UNSAT
The complement problem of SAT is called UNSAT and intuitively belongs to the class co-NP. Analogously to SAT, UNSAT is even co-NP-complete. UNSAT accepts a CNF Boolean formula as an input.
Definition 8.
UNSAT = [Abbildung in dieser Leseprobe nicht enthalten]is a CNF Boolean formula which is unsatisfiable} Input: A Boolean formula F in conjunctive normal form. Question: Is F unsatisfiable?
UNSAT asks whether a Boolean formula which is presented is always false.
For example, given [Abbildung in dieser Leseprobe nicht enthalten], it is obvious that this formula is always false, since either x = TRUE which leads to[Abbildung in dieser Leseprobe nicht enthalten] or vice versa. Therefore, it is not possible to find an assignment which would result in F being true.
2.4 Summary
The following figure presents an overview concerning the computational problems dis- cussed in this chapter. Every problem is assigned to the respective complexity class.
illustration not visible in this excerpt
Figure 2.5: Overview of the computational problems and the corresponding complexity.
Chapter 3 “Minesweeper is NP-complete”
3.1 Introducing the paper
This chapter shall explain the results of the paper “Minesweeper is NP-complete” by Richard Kaye1. It was the first to be published on this topic and has since provided the basis for other papers which are discussed here.
3.1.1 Minesweeper Consistency Problem MCP
According to Kaye1, the Minesweeper Consistency Problem (MCP ) can be described using the following question: “Is there a configuration of mines in the [rectangular] grid that would result in the pattern of symbols one sees (according to the [. . . ] Minesweeper rules)?”12
By posing this question it becomes clear that one can convert the difficulties the player faces during the game to a simple decision problem with yes or no answers. If there is “some pattern of mines in the blank squares that give[s] rise to the numbers seen”1, the data given is known to be consistent. If the answer is no, then no consistency can be determined.
Scott defines MCP formally as follows2:
Minesweeper Consistency
Input: A board configuration, with some digits and flagged mine locations.
Question: Does there exist a placement of mines that is consistent with the visible digits and flagged locations?
From now on, the problem of detecting which squares are certainly mines and which are definitely mine-free shall be deemed to be equivalent to the Minesweeper Consistency Problem14. To make sure that a field is mined, it has to be tested negative for the possible assignments ({0 . . . 8}), as numbers of adjacent mines are only shown, if the field does not contain a mine.
A square is definitely safe to be opened, if the square in question is marked with a mine and if running the Minesweeper Consistency Algorithm gives out the information that the data is inconsistent. However, should the outcome show that the data is consistent, it is possible that a mine is hidden in that very square. To examine whether or not the square in question contains numbers ({0 . . . 8}), the configuration has to be changed once more to the number of current interest and again, the Minesweeper Consistency Algorithm checks the data for consistency.
From these observations, Kaye concludes that M CP is equivalent to actually playing Minesweeper which leads to the assumption that the game itself is NP-complete. Scott1 agrees with Kaye that the M CP is one possible way of solving the Minesweeper game, but he also emphasizes that it is definitely not the only strategy for doing so2, which will be discussed in all its particulars in the following chapter.
3.1.2 MCP is in NP
Theorem 3.1. The Minesweeper Consistency Problem is in N P .
Proof. The polynomial-time certificate is a total function [Abbildung in dieser Leseprobe nicht enthalten] is the set of all board positions and L = {0, 1, . . . , 8, *}. A square x is free of mines if f (x) = i, i ∈ {0,...,8}. On the contrary, if a field contains a mine, f(x) = ∗ is true. As already mentioned, the input size of the certificate is polynomial, namely |X| = n, which is the number of all squares in the playing field.
The Minesweeper Consistency Algorithm works as follows:
1. Place mines and non-mines on the board as defined by f .
2. For each numerically labeled square check that it has exactly the correct number of mines adjacent to it.
As M C-algorithm scans each square exactly once, the worst case complexity of M CA is polynomial in n (in fact[Abbildung in dieser Leseprobe nicht enthalten], since the algorithm A is bounded both above big-O and below Ω by a constant) □ 17.
In concrete terms, NP-completeness of MCP means that heretofore there is no MCP - algorithm known which is more efficient than simply checking all of the 2n possible positions of mines (n = uncovered squares)13.
Interestingly, one can not say that the complementary Minesweeper Consistency Problem - i.e. whether some input configuration is inconsistent - is in NP or not14.
3.2 Reduction from SAT
SAT, as explained in 2.3.6, is the satisfiability problem of Boolean formulas and is known to be NP-complete. The aforementioned Minesweeper Consistency Problem by Kaye ( see chapter 3.1.1) is reducible from SAT, because based on the rules of the game, the characteristics of every single square in the grid can be described by a Boolean circuit.
3.2.1 Introduction to the Reduction
While am means that a mine is located in the field a, aj states that there is no mine at this field but j (0 ≤ j ≤ 8) mines located in the neighboring fields around a. The same is true for the other fields: (b, c, d, . . . , i).
illustration not visible in this excerpt
Figure 3.1: 3 x 3 field of uncovered squares.
According to the rules of the game, the square e can be described as follows:
1. It is obvious that (em, e0, e1, ..., e8) can all be potentially true, yet in fact only one of the statements is.
2. For (k ∈ {0, ..., 8}), with ek being true, exactly k of the statements (am, bm, ..., im) must be true.
One needs 90 inputs (am, a0, . . . , a8 . . . , im, i0, . . . , ı8) so that each instance of the condi- tion mentioned in the second statement can be represented as a Boolean formula. The whole configuration of the grid is only consistent, iff there is a combination of inputs that satisfies the circuit C. C is now defined as the conjunction of the Boolean expressions for each square on the grid17. It has to be kept in mind that for each square only one assignment can be true:
illustration not visible in this excerpt
3.3 Boolean Circuits in Minesweeper
This section will demonstrate how the basic Boolean circuits can actually be represented in Minesweeper. This is of importance for the polynomial reduction from SAT to M CP , so that NP-completeness can be proved.
Looking at figure 3.2, one easily recognizes that x and x′ are the only fields uncovered and dependent on each other. If x = TRUE, then x′ = FALSE and vice versa. Here, x = TRUE means that x contains a mine.
illustration not visible in this excerpt
Figure 3.2: A Wire.
This figure is a typical representation of a wire carrying a Boolean value ∈ {TRUE, FALSE}. From now on, the assigned direction for the wire is from left to right (or top-down respectively).
[...]