%
% Assignment 7a for CS3530 Computational Theory:
% Complexity
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{enumerate}

% 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{center}
\textbf{\Large CS 3530: Assignment 7a} \\[2mm]
Fall 2024
\end{center}

\raggedright

\section*{Problem 7.6 (10 points)}

\subsection*{Problem}

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

\emph{Hint:} As we discussed in class,
construct the language (e.g. $P_{CAT} = \{ \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 union.}

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

\section*{Problem 7.5 (10 points)}

Is the following formula satisfiable?  (Give your reasoning.)

$$(x \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor y) \land (\overline{x} \lor \overline{y})$$

\subsection*{Solution}


\end{document}
