2
$\begingroup$

There are two ways to define a probabilistic Turing Machine:

  1. A Turing Machine that can toss coins during its computation.
  2. A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is the original input and $r$ is taken from a distribution of coin tosses.

For example, Arora and Barak give an "alternative definition" for $\mathrm{BPP}$:

Definition 7.4 (BPP, alternative definition)
$\mathrm{BPP}$ contains a language $L$ if there exists a polynomial-time TM $M$ and a polynomial $p\colon \mathbb{N}\to \mathbb{N}$ such that for every $x \in \{ 0, 1 \}^{∗}$, $\Pr_{r \in \{ 0,1 \}^{p(|x|)}} [M (x, r) = L(x)]\geq 2 / 3 $.

My problem is formulating a similar alternative definition for $\mathrm{ZPP}$.

$\mathrm{ZPP}$ can be defined as the class of languages with a randomized algorithm that always outputs the correct answer, and for every input the expected running time of the algorithm is polynomial.

If we want a similar alternative definition for $\mathrm{ZPP}$, then $r$ should be an infinite stream because the algorithm may need to use any number of coin tosses before it finishes (with small probability).

Is there any problem with a Turing Machine that takes as a second input an infinite long stream?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/ZPP_(complexity) ​ ​ $\endgroup$ – user12859 Jul 7 '17 at 6:17
  • $\begingroup$ Though it is not a direct answer to your query, any Turing machine that takes an infinite input to achieve an output, would in the worst case require to read the complete infinite input. In other words it might not halt. $\endgroup$ – TheoryQuest1 Jul 7 '17 at 6:49
  • $\begingroup$ @TheoryQuest1 The probability for this to happen should be 0. For example, a ZPP algorithm that decides the language $\Sigma^*$ will toss coins until it sees $H$ and then accepts. The probability that it will not halt on an infinite random input is 0. $\endgroup$ – Nathan_ Jul 7 '17 at 7:37
  • $\begingroup$ If the probability is 0, then why would we need an input of infinite length in the first place as we are certain only a finite would be read and the rest never? $\endgroup$ – TheoryQuest1 Jul 7 '17 at 7:41
  • $\begingroup$ @TheoryQuest1 Because there's still a positive probability to have to read any number of bits before seeing an $H$ . So you can't bound the length of $r$ because $ZPP$ algorithms have to halt and output the correct answer with probability 1. $\endgroup$ – Nathan_ Jul 7 '17 at 8:16
2
$\begingroup$

The definition works fine if you allow $r$ to be infinite, and require that $M(x,r)$ agrees with $L$ with probability $1$ when $r$ is distributed according to the coin toss measure on $\{0,1\}^{\mathbb{N}}$ (toss a fair coin an infinite number of times). In this setting, in order to get $\mathsf{ZPP}$, you need to require that the expected running time will be polynomial in $|x|$.

However, you don't really need an infinite number of coins to get $\mathsf{ZPP}$, and could do with an exponential amount of coins. Suppose $L\in\mathsf{ZPP}$, hence there exists a probabilistic Turing machine $M(x)$, such that for all $x\in\Sigma^*$ it holds that $M(x)=L(x)$ and $\mathbb{E}[T_x]\le |x|^c$, where $T_x$ is the running time of $M$ on input $x$. You can now define an equivalent Turing machine $M'$ which is exponential in the worst case (rather than unbounded), and still satisfies the above conditions. Given input $x$, $M'$ simulates $M$ for $2^{|x|^c}$ steps, and if $M$ did not halt in this time, check "manually" if $x\in L$. This can be done by running a PSPACE machine for $L$ (which exists since $\mathsf{ZPP\subseteq PSPACE})$. You can now show that $M'$ is also polynomial in expectation (think about the appropriate choice of $c$ for this to work).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.