Minesweeper. Varianten und Komplexität


Bachelor Thesis, 2013

54 Pages, Grade: 2,0


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

Excerpt out of 54 pages

Details

Title
Minesweeper. Varianten und Komplexität
College
University of Hannover
Grade
2,0
Author
Year
2013
Pages
54
Catalog Number
V264848
ISBN (eBook)
9783656540878
ISBN (Book)
9783656541080
File size
9090 KB
Language
English
Keywords
minesweeper, varianten, komplexität
Quote paper
Polina Yakovleva (Author), 2013, Minesweeper. Varianten und Komplexität, Munich, GRIN Verlag, https://www.grin.com/document/264848

Comments

  • No comments yet.
Look inside the ebook
Title: Minesweeper. Varianten und Komplexität



Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free