%
% Assignment 7d for CS3530 Computational Theory:
% Complexity
% Fall 2023
%
% 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 7d} \\[2mm]
Fall 2023
\end{center}

\raggedright

\section*{Problem 7.33 (20 points)}

\subsection*{Problem}

In the following solitaire game, you are given an $m \times m$ board.  On each of its $m^2$ positions lies either a blue stone,
a red stone, or nothing at all.  You play by removing stones from the board until each column contains only stones of a
single color and each row contains at least one stone.  You win if you achieve this objective.  Winning may or may not be possible,
depending upon the initial configuration.  Let $\textsc{Solitaire} = \{ G | G $ is a winnable game configuration $\}$. Prove
that \textsc{Solitaire} is NP-complete.

\emph{Hint:} This is an ``A'' problem from the text.  They have provided a solution, with a reduction from \textsc{3SAT}.

\emph{Note:} In order to receive credit for this assignment, you must complete the full NP-completeness proof process outlined here.


\subsection*{Prove \textsc{Solitaire} $\in$ NP}

\subsubsection*{Describe a certificate for \textsc{Solitaire}}
\subsubsection*{Provide a polynomial verifier for \textsc{Solitaire}}

\subsection*{Prove \textsc{Solitaire} is NP-hard}

Given that \textsc{3SAT} is NP-complete,
show that $\textsc{3SAT} \le_P \textsc{Solitaire}$ with the following steps.

\subsubsection*{Provide reduction from \textsc{3SAT} to \textsc{Solitaire}}

\subsubsection*{Prove reduction from \textsc{3SAT} to \textsc{Solitaire} is polynomial}

\subsubsection*{Show \textsc{3SAT} has a satisfying assignment if \textsc{Solitaire} is winnable}

\subsubsection*{Show \textsc{Solitaire} is winnable if \textsc{3SAT} has a satisfying assignment}

\subsubsection*{Conclude that \textsc{Solitaire} is NP-hard}

\subsection*{Conclude that \textsc{Solitaire} is NP-complete}



\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
