%
% Assignment 8d for CS3530 Computational Theory:
% Complexity
% Fall 2017
%
% Problems taken from Sipser
%
\documentclass{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}
\usepackage{enumerate}
\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi
\empaddtoTeX{\usepackage{amsmath}}
\empprelude{input boxes; input theory}
% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom
% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}
\begin{document}
\begin{empfile}
\begin{center}
\textbf{\Large CS 3530: Assignment 8d} \\[2mm]
Fall 2017
\end{center}
\raggedright
\section*{Problem 7.30 (20 points)}
\subsection*{Problem}
This problem is inspired by the single-player game
\textit{Minesweeper}, generalized to an arbitrary graph. Let $G$ be
an undirected graph, where each node either contains a single,
hidden \textit{mine} or is empty. The player chooses nodes, one by
one. If the player chooses a node containing a mine, the player
loses. If the player chooses an empty node, the player learns the
number of neighboring nodes containing mines. (A neighboring node is
one connected to the chosen node by an edge.). The player wins if
and when all empty nodes have been so chosen.
In the \textit{mine consistency problem} you are given a graph $G$,
along with numbers labeling some of $G$'s nodes. You must determine
whether a placement of mines on the remaining nodes is possible, so
that any node $v$ that is labeled $m$ has exactly $m$ neighboring
nodes containing mines. Formulate this problem as a language and
show that it is NP-complete.
\subsection*{Solution}
\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}