%
% Assignment 8c 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 8c} \\[2mm]
Fall 2017
\end{center}
\raggedright
\section*{Problem 7.26 (20 points)}
\subsection*{Problem}
You are given a box and a collection of cards as indicated in the
figure on page 297 of Sipser 2nd edition, page 325 of Sipser 3rd
edition. Because of the pegs in the box and the
notches in the cards, each card will fit in the box in either of two
ways. Each card contains two columns of holes, some of which may not
be punched out. The puzzle is solved by placing all the cards in the
box so as to completely cover the bottom of the box, (i.e., every
hole position is blocked by at least one card that has no hole
there.) Let \textsc{Puzzle} $=\{\langle c_1,\ldots,c_k\rangle:$ each
$c_i$ represents a card and this collection of cards has a
solution$\}$. Show that \textsc{Puzzle} is NP-complete.
\subsection*{Solution}
\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}