Bachelorarbeit, 2013
54 Seiten, Note: 2,0
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
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare