Minesweeper. Varianten und Komplexität

Bachelor Thesis , 2013 , 54 Pages , Grade: 2,0

Computer Science - Applied

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].

Inhaltsverzeichnis (Table of Contents)

• Introduction
  • Overview
• The Basics
  • What is Minesweeper?
  • Complexity theory: complexity classes
    • The complexity class NP
    • The complexity class P
    • The complexity class co-NP
    • Possible relations among the complexity classes P, NP and co-NP
    • The hierarchy of complexity classes
  • Complexity theory: problem instances
    • Decision problems as formal languages
    • What does decidability mean?
      • A simple example for a decidable language
      • How to prove the language ADF A to be decidable
    • What does reducibility mean?
    • What does NP-hard mean?
    • What is completeness?
      • How to show that a problem is NP-complete
      • How to show that a problem is co-NP-complete
    • Satisfiability SAT
    • Unsatisfiability UNSAT
  • Summary
• “Minesweeper is NP-complete”
  • Introducing the paper
    • Minesweeper Consistency Problem MCP
    • MCP is in NP
  • Reduction from SAT
    • Introduction to the Reduction
  • Boolean Circuits in Minesweeper
  • Composing circuits with basic building blocks in Minesweeper syntax
    • An AND-gate in Minesweeper
    • An OR-gate in Minesweeper
  • Summary
• “Minesweeper May Not Be NP-complete But Is Hard Nonetheless”
  • Introducing the Paper
  • Minesweeper Inference Problem MIP
    • MIP search
    • MIP decision
  • Minesweeper Inference MIP is in co-NP
    • Reduction from UNSAT
      • Converting the Input: F ↔ F’
      • Construction of the Boolean circuit
      • Construction of the board
    • Correctness of the reduction
    • Reduction from UNSAT explained with a concrete example
  • Summary

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This bachelor thesis explores the computational complexity of the popular game Minesweeper. The main objective is to analyze the game from a complexity theory perspective, investigating its relationship with prominent complexity classes such as NP and co-NP. The thesis aims to demystify the notion of NP-completeness in the context of Minesweeper, highlighting the work of Kaye and Scott in this field. The key themes investigated include:

• The Minesweeper Consistency Problem (MCP) and its NP-hardness
• The Minesweeper Inference Problem (MIP) and its co-NP-completeness
• The implications of these findings for the P vs. NP problem and the NP vs. co-NP problem
• The practical relevance of complexity theory in game design and real-world applications

Zusammenfassung der Kapitel (Chapter Summaries)

• Chapter 2 introduces the game Minesweeper and fundamental concepts from complexity theory, including complexity classes, decidability, reducibility, completeness, and the problems SAT and UNSAT.
• Chapter 3 examines Kaye's work, which claimed that Minesweeper is NP-complete. This chapter explains Kaye's Minesweeper Consistency Problem and its NP-hardness proof, demonstrating how Boolean circuits can be represented in Minesweeper.
• Chapter 4 delves into Scott's paper, which refutes Kaye's claim. It introduces the Minesweeper Inference Problem and proves its co-NP-completeness. This chapter also provides a detailed explanation of the reduction from UNSAT to MIP.

Schlüsselwörter (Keywords)

This bachelor thesis investigates the complexity of the game Minesweeper, focusing on its relationship with key complexity classes. The main concepts explored include NP-completeness, co-NP-completeness, Minesweeper Consistency Problem (MCP), Minesweeper Inference Problem (MIP), Boolean circuits, reduction, and the P vs. NP problem.

• College: University of Hannover
• Grade: 2,0
• Author: Polina Yakovleva (Author)
• Publication Year: 2013
• Pages: 54
• Catalog Number: V264848
• ISBN (eBook): 9783656540878
• ISBN (Book): 9783656541080
• Language: English
• Tags: minesweeper, varianten, komplexität