\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{graphicx, epsfig}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newcommand{\polyL}{\mbox{PolyLog}}
\newcommand{\Poly}{\mbox{P}}
\newcommand{\NL}{\mbox{NL}}
\newcommand{\SPACE}{\mbox{SPACE}}
\newcommand{\SC}{\mbox{PolyLogSpacePolyTime}}

\head{CSG714}{Theory of Computation}{Spring 2009}{24 March 2009}{15}

\begin{center}
\Large{\bf Problem Set 5 (due Tuesday, April 7)}
\end{center}

{\bf 0.} Problem 4 of PS 4.

{\bf 1. (10 points) Probability Amplification}

Problem 10.11 of Sipser.

{\bf 2. (10 points) Cover time of a random walk} 

In class, we showed that for any node a random walk on an undirected
graph takes an expected $O(n^3)$ steps to reach all nodes of the
graph.  In this exercise, we prove this is asymptotically tight.

Consider a graph with $2n$ nodes, $n$ of which form a clique and the
other $n$ form a path.  A node of the clique and an endpoint of the
path are connected by an edge.  Show that the random walk algorithm
applied to this graph takes expected $\Omega(n^3)$ time to reach all
nodes.

{\bf 3. (10 points) Probabilistic method for SAT}

Let $n$ and $k$ be two integers.  Suppose you have a SAT formula with
fewer than $n^k$ clauses, each having at least $k \log(n)$ distinct
variables (i.e., no two literals in a clause correspond to the same
variable).  Show that a random assignment satisfies the formula with
non-zero probability, thus proving that the formula has a satisfying
truth assignment.  Give a polynomial-time algorithm to compute a
satisfying assignment.  (By polynomial time, we mean time polynomial
in the input size.)

{\bf 4. (10 points) SAT, RP, and BPP}

Show that if SAT is in BPP, then SAT is in RP.

{\bf 5. (20 points) BP- and R-machines} 

Given a string $w$, it is decidable to determine whether $w$ is a
valid description of a nondeterministic Turing machine (in a specified
language).  Similarly, given a string $w$, it is decidable to
determine whether $w$ is a valid description of a deterministic Turing
machine.

Let us see whether similar properties hold for Turing machines that
form the probabilistic complexity classes we have studied.  Define a
{\em BP-machine}\/ to be a nondeterministic Turing machine $M$ in
which for every string $w$, either at least two-third of its
computation paths on $w$ accept or at least two-third of its
computation paths on $w$ reject.  Define an {\em R-machine}\/ to be a
nondeterministic Turing machine $M$ in which for every string $w$,
either at least half of its computation paths on $w$ accept or all of
its computation paths on $w$ reject.

Is the set of all BP-machines decidable?  Recognizable?

Is the set of all R-machines decidable?  Recognizable?
\end{document}
