%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{#1}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
\hfill Winter 2018} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Problem Set #1 \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
\vspace{2mm}}
}
\end{center}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\begin{document}
\problemset{5}{February 14}{\bf {February 21}}
Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the text (Sipser). The
full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item A graph $G$ is called {\em $k$-colorable} if there is a way
to assign a color to each vertex so that no edge has both
endpoints assigned the same color, using at most $k$ distinct
colors.
\begin{enumerate}
\item
Show that the language
\[\mbox{{\sc 2-colorable}} = \{G : G \mbox{ is 2-colorable}\}\]
is in P by reducing it to a problem known to be in P.
\item
Show that the following language is NP-complete:
\[\mbox{{\sc 3-colorable}} = \{G : G \mbox{ is 3-colorable}\}.\]
Hint: reduce from 3-SAT. Your graph will contain 1 vertex for each
literal, and 3 special vertices connected in a triangle (which
must then be colored with the three distinct colors). You may find
this observation useful: in the following graph,
\vspace{.1in}
\epsfclipon
\setlength{\epsfxsize}{2in}
\centerline{\epsfbox{gadg1.eps}}
if each of the grey nodes are colored with one of two colors, then
it is possible to extend this coloring to a 3-coloring if and only
if at least one of the three grey nodes on the left has the same
color as the one on the right.
\end{enumerate}
\item Let $(3, 3)$-SAT be the language consisting of satisfiable
CNF formulas with at most 3 literals per clause, {\em and} at most
3 occurrences of any variable. Show that $(3, 3)$-SAT is
NP-complete.
\item {\sc max2sat} is the language consisting of all pairs
$(\phi, k)$ where $\phi$ is a 2-CNF formula for which it is
possible to simultaneously satisfy at least $k$ clauses. Show that
{\sc max2sat} is NP-complete. Hint: how many of the following
clauses can be satisfied as a function of $x, y$ and $z$?
\begin{eqnarray*}
& & (x \lor x), (y \lor y), (z \lor z), (w \lor w), \\
& & (\neg x \lor \neg y), (\neg y \lor \neg z), (\neg z \lor \neg
x), \\
& & (x \lor \neg w), (y \lor \neg w), (z \lor \neg w)
\end{eqnarray*}
\end{enumerate}
\end{document}