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

heoremstyle{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}

egin{document}

egin{center}

{Large CS 535: Complexity Theory, Fall 2020}

igskip

{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

egin{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

egin{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.)

egin{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 $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

egin{problem}[Consequences of $NL = coNL$] hfill

egin{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

angle$ 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$ extbf{and there is no shorter path}.) Prove that $mathprob{DLEN}$ is $NL$-complete. (6 points)

end{enumerate}

end{problem}

medskip

egin{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) o x_1$.

egin{enumerate}[(a)]

item Define the language $mathprob{IMPSAT} = {varphi mid varphi ext{ 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}