Minesweeper. Varianten und Komplexität

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