%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the “author” and “collaborators” fields as
% appropriate. Write your solutions where indicated.
%
\def\inclsolns{0}
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\input{macros}
\theoremstyle{definition}
\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi
\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother
\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}
\begin{document}
\begin{center}
{\Large CS 535: Complexity Theory, Fall 2020}
\bigskip
{\Large Homework 4}
\smallskip
Due: 8:00PM, Friday, October 9, 2020.
\end{center}
\ifnum\inclsolns=1
\makeatletter
\noindent Name: \@author \\
Collaborators: \@collaborators
\makeatother
\else
\fi
\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.
\medskip
\begin{problem}[“Mid”-Semester Feedback Form]
Please fill out the feedback form here: \url{https://forms.gle/YdQ2tqHsfbM6VcxH9}. (It’s anonymous, so we can’t check whether you did it, but we value your voice!)
\end{problem}
\medskip
\begin{problem}[Time vs. Space] As usual, you can quote anything stated in the main body of Arora-Barak or during the lectures to solve these problems. (Which may give some of them very short solutions.)
\begin{enumerate}[(a)]
\item Show that $\NL \subseteq \P$. (2 points)
\item Define $\class{PolyL} = \cup_{c = 1}^\infty \SPACE(\log^c n)$. Show that $\NL \subseteq \class{PolyL}$. (2 points)
\item Prove that there are no $\class{PolyL}$-complete problems (with respect to logspace reductions). Hint: Assume that such a complete problem were to exist. Show that it would contradict the space hierarchy theorem. (4 points)
\item Define the class $\class{SC}$ (“Steve’s Class,” in honor of Stephen Cook) to consist of all languages $A$ for which there exists a deterministic TM $M$ deciding $A$ that runs in time $\poly(n)$ and uses space $\poly\log(n)$. It is an open question whether $\NL \subseteq \class{SC}$. Explain why parts (a) and (b) together do not resolve this open question. (2 points)
\end{enumerate}
\end{problem}
\medskip
\begin{problem}[Consequences of $\NL = \coNL$] \hfill
\begin{enumerate}[(a)]
\item Let $S(n) \ge \log n$ be a space-constructible function. Show that $\NSPACE(S(n)) = \class{coNSPACE}(S(n))$. (4 points)
\item Define the language $\mathprob{DLEN}$ to consist of all tuples $\langle G, s, t, d\rangle$ where $G$ is an directed graph, and the distance from $s$ to $t$ in $G$ is exactly $d$. (That is, there exists a path from $s$ to $t$ of length $d$ \textbf{and there is no shorter path}.) Prove that $\mathprob{DLEN}$ is $\NL$-complete. (6 points)
\end{enumerate}
\end{problem}
\medskip
\begin{problem}[*Bonus Problem* Implication SAT]
An “implication CNF” is a CNF where every clause has at most one positive variable. For example, $(x_1 \lor \overline{x_2} \lor \overline{x_3}) \land (x_4 \lor \overline{x_1} \lor \overline{x_2})$ is an implication CNF, but $(x_1 \lor x_2 \lor \overline{x_3}) \land (x_4 \lor \overline{x_1} \lor \overline{x_2})$ is not. The name comes from the (useful) fact that the logical expression $x_1 \lor \overline{x_2} \lor \dots \lor \overline{x_k}$ is equivalent to $(x_2 \land \dots \land x_k) \to x_1$.
\begin{enumerate}[(a)]
\item Define the language $\mathprob{IMPSAT} = \{\varphi \mid \varphi \text{ is a satisfiable implication CNF}\}$. Prove that $\mathprob{IMPSAT}$ is $\P$-complete under logspace reductions.
\item What goes wrong in your proof if you use it to try to show that $\mathprob{IMPSAT}$ is $\NP$-complete?
\end{enumerate}
Hint: You can make the same kinds of simplifying assumptions that we made in our proof sketch of the Cook-Levin Theorem from class—single-tape TM, binary tape alphabet, input padded with trailing zeroes. Focus more on the main ideas than on the details.
\end{problem}
\end{document}