[SOLVED] CS %

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

definclsolns{0}
documentclass[12pt]{article}

usepackage{fullpage}
usepackage{graphicx}
usepackage{enumerate}
usepackage{comment}
usepackage{amsmath,amssymb,amsthm}
usepackage{hyperref}

input{macros}

theoremstyle{definition}

ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi

makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators 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}

ifnuminclsolns=1
makeatletter
oindent 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}. (Its anonymous, so we cant 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)]
itemShow 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}$ (Steves 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 $polylog(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, drangle$ 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 classsingle-tape TM, binary tape alphabet, input padded with trailing zeroes. Focus more on the main ideas than on the details.
end{problem}
end{document}