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

\raggedright

\section*{Problem 7.22 (20 points)}

\subsection*{Problem}

Let $\textsc{Double-Sat} = \{ \phi | \phi $ has at least two satisfying assignments $\}$. Show that
\textsc{Double-Sat} is NP-complete.

\emph{Hint:} Consider a reduction from \textsc{Sat} or \textsc{3Sat}.

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

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