%
% Assignment 7b 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 7b} \\[2mm]
Fall 2023
\end{center}

\raggedright


\section*{Problem 7.6 (10 points)}

\subsection*{Problem}

Show that $P$ is closed under complement.

\emph{Hint:} As we discussed in class,
construct the language (e.g. $PCAT = \{ \langle P_1,P_2,w \rangle | P_1,P_2 \in P $ and $ w $ is a string,  $ w = x \cdot y $, $ x \in P_1 $ and $ y \in P_2 \}$),
then provide a deterministic machine that decides the language in polynomial time.

\subsection*{Solution to P closed under complement.}


\section*{Problem 7.7 (10 points)}

\subsection*{Problem}

Show that $NP$ is closed under union and concatenation.

\emph{Hint:} As we discussed in class,
construct the language (e.g. $NPCAT = \{ \langle NP_1,NP_2,w \rangle | NP_1,NP_2 \in NP $ and $ w $ is a string,  $ w = x \cdot y $, $ x \in NP_1 $ and $ y \in NP_2 \}$),
then describe a certificate and a verifier that deterministically verifies the certificate in polynomial time.

\subsection*{Solution to NP closed under union.}

\subsection*{Solution to NP closed under concatenation.}


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