\documentstyle[11pt,abstract]{article}
\headheight 0pt
\setlength{\textwidth}{6.50in}          % normal width of text on page
\setlength{\oddsidemargin}{0in}   % left margin less 1 inch, odd #'ed pgs
\setlength{\evensidemargin}{.25in}  % right margin less 1 inch, even #'ed pgs
\input math
\newcommand{\rarrow}{\rightarrow}
\newcommand{\darrow}{\leftrightarrow}
\renewcommand{\phi}{\varphi}
\begin{document}
\pagestyle{empty}

\begin{center}
{\Large COMP 409\\
Assignment No. 3}\\
\bigskip
{\bf Due date: October 12, 2021}
\end{center}
\bigskip

\noindent
{\bf Note}:
\begin{enumerate}
\item
The submitted assignment needs to be typeset in LaTeX.
\item
{\bf Teamwork}: You are expected to complete this assignment in teams.
By signing your name on the assignment you are asserting
that the work submitted was done collaboratively, and that you have
adhered to Rice's Honor Code.
At the very least, this entails:
\begin{itemize}
\item
discussing each problem and agreeing on a sketch of the solution,
\item
reviewing the written solutions for technical correctness and
typographical errors,
\item
doing a joint codewalk over all written programs,
\item
dividing labor equally (roughly), and
\item
being able to explain every answer as if it is your own answer.
\end{itemize}
\item
Note on the submission the total number of hours put in by
each partner separately and by the two partners together.
\end{enumerate}

\bigskip

\noindent
{\sf NP-completeness}:
\begin{enumerate}
\item
The {\em exact cover by 3-sets problem} is as follows.
You are given a finite set $X$ and a collection $C$ of 3-element
subsets of $X$. You have to decide whether $C$ has an
{\em exact cover}, i.e., a subcollection $C' \subseteq C$ such that
every element of $X$ occurs in exactly one member of $C'$.

Show that this problem can be polynomially reduced to SAT.

\item
The \emph{Interger Programming} (IP) problem is to check
whether a system of linear inequalities, with integral coefficients,
has an integral solution. Show that this problem is NP-hard by
reducing 3-SAT to it.

\item
A problem $L\subseteq \Sigma^*$ is in co-NP if there is a polynomial
$p$ and a polynomial-time algorithm $A$ such that for all
$x\in\Sigma^*$ the following holds
\begin{quote}
$x\not\in L$ iff there exists some $y\in \Sigma^{\leq p(|x|)}$ such
that $A(x,y)=1$.
\end{quote}
The problem $L$ is co-NP-complete if $L$ is in co-NP and
for all $L'$ in co-NP we have that $L' \leq_p L$.
\begin{enumerate}
\item
Show that $L$ is in co-NP iff $\Sigma^* -L$ is in NP.
\item
Show that $L$ is co-NP-complete iff $\Sigma^* -L$ is NP-complete.
\item
Show that if $L$ is co-NP complete and L is in NP, then
NP=co-NP.
\end{enumerate}
\end{enumerate}


\noindent
{\sf Satisfiability}:
\begin{enumerate}
\item
Prove that for $\varphi\in \mbox{\sf Form}$, $\tau \in 2^{AP(\varphi)}$,
and $p\in AP(\varphi)$, we have that $\tau\models\varphi$ iff 
$\tau |_{AP(\varphi)-\{p\}} \models \varphi[p\mapsto\tau(p)]$.
\item
Prove, using only de Morgan's laws and the distributive laws
(for $\wedge$ and $\vee$)
that every formula is equivalent to a formula in 
{\em conjunctive normal form} (CNF), i.e., 
a conjunction of disjunctions of literals.
(Recall that a \emph{literal} is an atomic proposition or 
a negated atomic proposition.)
Show that if there is a poly-time algorithm that translate each
formula to its conjunctive normal form, then $P=NP$.
\item
{\sf Boole's Example 5}: The following problem was posed by Boole in 1854.
\begin{quote}
Let the observation of a class of natural productions be supposed
to have led to the following general results. 

1st, That in whichsoever of these productions the properties A and C are 
missing, the property E is found, together with one of the properties B 
and D, but not with both. 

2nd, That wherever the properties A and D are found while E is
missing, the properties B and C will either both be found or both be 
missing. 

3rd, That wherever the property A is found in conjunction with either B or 
E, or both of them, there either the property C or the property D will be 
found, but not both of them.  And conversely, wherever the property C or D 
is found singly, there the property A will be found in conjunction with 
either B or E, or both of them. 

Let it then be required to ascertain, first, what in any particular instance
may be concluded from the ascertained presence of the property A, with 
reference to the properties B, C, and D; also whether any
relations exist independently among the properties B, C, and D.
Secondly, what may be concluded in like
manner respecting the property B, and the properties A, C, and D.
\end{quote}
Formalize Boole's example using a modern terminology and solve it,
using an implementation of the splitting method (attach the code)
(focus on code elegance rather than speed).
\end{enumerate}

\noindent
{\sf Adequacy} (see lectures notes on ``Formulas and Circuits'')
%and ``Automata for SAT'')
\begin{enumerate}
\item
Let {\sf ttof} be a ternary connective such that
${\sf ttof}(p_1,p_2,p_3)$ is true iff $3p_1 + 2p_2 +p_3 \ge 4$.
Write a $\{\neg,\wedge,\vee\}$-formula that is logically equivalent
to ${\sf ttof}(p_1,p_2,p_3)$.
\item
Let {\sf succ-carry} be a $3n$-ary connective such that
{\sf succ-carry}$({\bf p},{\bf c},{\bf q})$ is true,
for ${\bf p}=\langle p_1,\ldots,p_n \rangle$,
${\bf c}=\langle c_1,\ldots,c_n \rangle$, and
${\bf q}=\langle q_1,\ldots,q_n \rangle$,
when ${\bf q}$ is obtained by adding $1$ to ${\bf p}$ (modulo $2^n$)
with ${\bf c}$ being the carry.
Write a $\{\neg,\wedge,\vee\}$-formula of size $O(n)$ that is
logically equivalent to
{\sf succ-carry}$({\bf p},{\bf c},{\bf q})$.
%Describe a DFA with $O(n)$ states that accepts precisely all
%truth assignments satisfying this formula (choose the order of
%the atomic propositions wisely).
\item
Prove that $\{\vee,\wedge\}$ is \emph{not} adequate.
\item
Let the binary connective $\downarrow$ mean ``nor''
(i.e., $p \downarrow q$ holds if neither $p$ nor $q$ hold), and
let the binary connective $\vert$ mean ``not both''
(i.e., $p \vert q$ holds if not both $p$ and $q$ hold).
Write a truth table for $\downarrow$ and $\vert$ and
prove that both $\{\downarrow\}$ and $\{\vert\}$ are adequate.
\item
Let {\sf false} by a 0-ary connective such that $\tau({\sf false})=0$
for all truth assignments $\tau$. Show that 
$\{{\sf false}, \rightarrow\}$ is adequate.
\item
Let the binary connective $+$ mean ``exclusive or''
(i.e., $p+q$ holds if precisely one of $p$ and $q$ hold).
Write a truth table for $+$ and prove that $\{+\}$ is not adequate.
\end{enumerate}

%\noindent
%{\sf Automata}:
%Let $A=(\Sigma,S,s_0,\rho,F)$ be a DFA. Its \emph{digraph}
%$G_A=(S,E)$, consists of the states of $A$ as nodes, and 
%an edge set $E=\{(s,t)~:~ t\in\rho(s,a) \mbox{ for some } a\in\Sigma\}$.

%Show that $L(A)\not=\emptyset$ iff there is a path in $G_A$ from $s_0$
%to some state in $F$. (Recall that a path in a digraph $(V,E)$ is
%a sequence $v_0,\ldots,v_n$ of nodes in $V$, $n\geq 0$, such that
%$(v_i,v_{i+1})\in E$ for $0\leq i < n$.)
\end{document}
