<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
\documentclass[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}
\usepackage{graphicx}


%
% 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 2025} }
       \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]}


% 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}}


% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:


\begin{document}
\problemset{5}{February 19}{\bf {February 26}}


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 Please turn in your solutions via
  Gradescope, by 1pm on the due date.}


\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}
           \centerline{\includegraphics[width=0.4\textwidth, angle=0]{gadg1.pdf}}

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*}
&amp; &amp; (x \lor x), (y \lor y), (z \lor z), (w \lor w),  \\
&amp; &amp; (\neg x \lor \neg y), (\neg y \lor \neg z), (\neg z \lor \neg
x), \\
&amp; &amp;  (x \lor \neg w), (y \lor \neg w), (z \lor \neg w)
\end{eqnarray*}


\end{enumerate}


\end{document}
</pre></body></html>