# 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

egin{document}

egin{center}
{Large CS 535: Complexity Theory, Fall 2020}

igskip

{Large Homework 9}

smallskip

Due: 2:00AM, Saturday, December 5, 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.

igskip

egin{problem}[Perfect Interactive Proofs] For parameters \$c, s ge 0\$, define the class \$MA_{c, s}\$ to consist of Merlin-Arthur interactive proofs with completeness probability \$c\$ and soundness probability \$s\$. That is, a language \$L in MA_{c, s}\$ if there exists a probabilistic poly-time verifier \$V\$ and a polynomial \$m(n)\$ such that
egin{align*}
x in L &implies exists u in zo^{m(n)} Pr[V(x, u) = 1] ge c \
x
otin L &implies forall u in zo^{m(n)} Pr[V(x, u) = 1] le s.
end{align*}
Recall that in class we defined \$class{MA} = class{MA}_{2/3, 1/3}\$.
egin{enumerate}[(a)]

item Prove that \$MA_{1, 1/3} = MA\$. That is, we may assume Merlin-Arthur proofs have perfect completeness probability. Hint: Modify the proof of the Sipser-G'{a}cs Theorem (Theorem 7.15). (6 points)

egin{solution}
end{solution}

item Prove that \$MA_{2/3, 0} = NP\$. That is, Merlin-Arthur proofs with perfect soundness are no more powerful than deterministic proofs. (4 points)
egin{solution}
end{solution}

item *Bonus* Prove the same relationships for general interactive proofs. That is, show that \$IP_{1, 1/3} = IP\$ and \$IP_{2/3, 0} = NP\$.
egin{solution}
end{solution}
end{enumerate}
end{problem}

igskip

ewcommand{perm}{operatorname{perm}}
egin{problem}[Counting \$k\$-Colorings]
Let \$G = ([n], E)\$ be a graph on \$n\$ vertices. A \$k\$-coloring of \$G\$ is a vector of colors \$(c_1, dots, c_n) in [k]^n\$ such that for every edge \$(i, j) in E\$, we have \$c_i
e c_j\$.
end{problem}

egin{enumerate}[(a)]

item Show that there is a rational polynomial \$p\$ of degree \$poly(k, n)\$ such that the number of \$k\$-colorings of a graph \$G\$ is given by
[sum_{c_1 = 1}^k sum_{c_2 = 1}^k ldots sum_{c_n = 1}^k p(c_1, dots, c_n).]
Hint: url{https://en.wikipedia.org/wiki/Lagrange_polynomial}. (4 points)

egin{solution}