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

\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{4}{February 12}{\bf {February 19}}


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
$[$worth 6 pts$]$ This problem concerns that language TILE, defined as
follows. Informally, an instance is a collection of $k$ {\em tile types}, together with a list of {\em horizontally
compatible} pairs of tile types, and a list of {\em vertically
compatible} pairs of tile types. An $n \times n$ {\em tiling} is a
placement of tiles into an $n \times n$ grid, so that every pair
of horizontally adjacent tiles is horizontally
compatible, and every pair of vertically adjacent tiles
is vertically compatible; in addition we
require that the tile in the upper left corner is tile type $1$. The
language TILE consists of all those instances for which there exists
an $n \times n$ tiling for all $n \ge 0$.

Formally, the language TILE is the set of those tuples \[\langle
k, H \subseteq [k] \times [k], V \subseteq [k] \times [k] \rangle\] for which the following holds. For all $n \ge 1$
there exists a function $f:[n]\times[n] \rightarrow [k]$ for
which:
\begin{itemize}
\item $f(1,1) = 1$, and

\item $(f(x, y), f(x, y+1)) \in H$ for all $1 \le x \le n$, and $1 \le y \le n-1$,
and

\item $(f(x, y), f(x+1, y)) \in V$ for all $1 \le x \le n-1$ and $1 \le y \le n$.
\end{itemize}

Here, $[n]$ is shorthand for the set $\{1,2,3,\ldots, n\}$. Prove
that TILE is undecidable by giving a reduction from
$\overline{\mbox{HALT}}$ (the complement of the language HALT).
In other words, give a function $R$ mapping instances of $\overline{\mbox{HALT}}$ to instances of TILE, with the property that $R(\langle M, w \rangle)$ is in the language TILE if and only if $\langle M, w \rangle$ is in the language $\overline{\mbox{HALT}}$. Hint: it will be helpful to ``name'' some of your tiles with
triplets of symbols.
\item Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are
{\em isomorphic} if there is a bijection $f:V_1 \rightarrow V_2$
such that $(u, v) \in E_1 \Leftrightarrow (f(u), f(v)) \in E_2$.
For a given graph $H$, define the following language:
\[\mbox{\sc contains}_{H} = \{G : G \mbox{ contains a subgraph isomorphic to $H$}\}.\]
Here by ``subgraph'' we mean a subset of $G$'s vertices together
with all of $G$'s edges on that subset of vertices -- often called
an ``induced subgraph.'' Prove that for every $H$,
$\mbox{CONTAINS}_H$ is in P.

\item Show that the following problem is in P:
\[\mbox{\sc unary subset sum} = \left \{(1^B, x_1,x_2, \ldots, x_n) : \exists \mbox{ a multiset } I \mbox{ of } [n]
\mbox{ for which } \sum_{i \in I} x_i = B \right \}.\] Here the
$x_i$ are all positive integers, as is $B$, and $[n]$ is shorthand
for the set $\{1,2,3,\ldots, n\}$. The notation $1^B$ means a
string of $B$ ones, which is the representation of $B$ in unary.
Hint: solve the problem for all $B' \le B$.



\end{enumerate}

\end{document}