<p>Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects the running time by at most a polynomial factor (the exact factor depending on the model of computation), and so the new machine is also in ZPP. The new machine is also guaranteed to always halt. So bounded-ZPP is the same class as ZPP.</p>

CC BY-SA 3.0
2017-09-01T16:13:11.647Z
Thank you. What if one would further restrict ZPP, requiring the PTM to halt in polynomial time? (Does it equal ZPP or P? Or is it a complexity class in its own right?)
John Smith
CC BY-SA 3.0
2017-09-01T19:16:19.137Z
Then you'll just get P.
Yuval Filmus
CC BY-SA 3.0
2017-09-01T19:17:33.070Z
@JohnSmith If the machine has to halt in polynomial time, and cannot make an error, it is effectively a deterministic polynomial-time machine. Thus, your class equals P.
Emil Jeřábek
CC BY-SA 3.0
2017-09-01T14:23:51.077Z
2017-09-01T14:23:51.077Z
Yuval Filmus
<p>I am writing a paragraph on the power of randomness, part of which I am trying to ground in theory of computation (I am no expert/researcher in this field). </p>

<p>First off, I am aware that for traditional complexity classes such as ZPP and BPP, it is open question whether they equal P. In context of this question, I am interested in a particular subset of ZPP.</p>

<p>Let ZPP be the set of decision problems for which there exists a Probabilistic Turing Machine (PTM) which solves it in a time that is polynomial <em>in expectation</em>.</p>

<p>Note that this definition allows indefinite computation (albeit with an infinitesimal likelihood). In fact, most membership proofs by example (I am aware of) use PTMs which exploit this fact.</p>

<p>Let bounded-ZPP (my own term) be the subclass of ZPP which (in addition) requires a PTM to have a bounded execution, i.e. it to halt after a finite (possibly super-polynomial) # steps.</p>

<p>I was wondering about the following:</p>

<ol>
<li><p>Is there a more conventional name for bounded-ZPP?</p></li>
<li><p>Is bounded-ZPP = ZPP?</p></li>
<li><p>Is P = bounded-ZPP?</p></li>
<li><p>If (3) holds, wouldn't this suggest that a hypothetical P $\subset$ ZPP, would be more correctly attributed to allowing indefinite execution in ZPP, rather than the "power of random choice"?</p></li>
</ol>

<cc.complexity-theory><complexity-classes><probabilistic-computation>
Power of randomness vs. power of indefinite computation
John Smith
# Power of randomness vs. power of indefinite computation

(Asked by: username_0 on 2017-09-01)

I am writing a paragraph on the power of randomness, part of which I am trying to ground in theory of computation (I am no expert/researcher in this field).

First off, I am aware that for traditional complexity classes such as ZPP and BPP, it is open question whether they equal P. In context of this question, I am interested in a particular subset of ZPP.

Let ZPP be the set of decision problems for which there exists a Probabilistic Turing Machine (PTM) which solves it in a time that is polynomial *in expectation*.

Note that this definition allows indefinite computation (albeit with an infinitesimal likelihood). In fact, most membership proofs by example (I am aware of) use PTMs which exploit this fact.

Let bounded-ZPP (my own term) be the subclass of ZPP which (in addition) requires a PTM to have a bounded execution, i.e. it to halt after a finite (possibly super-polynomial) # steps.

I was wondering about the following:

1. Is there a more conventional name for bounded-ZPP?
2. Is bounded-ZPP = ZPP?
3. Is P = bounded-ZPP?
4. If (3) holds, wouldn't this suggest that a hypothetical P $\subset$ ZPP, would be more correctly attributed to allowing indefinite execution in ZPP, rather than the "power of random choice"?

**Tags:** cc.complexity-theory, complexity-classes, probabilistic-computation


---

## 1 answers

### Answer by username_1 on 2017-09-01. Score: 13 | Accepted answer

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects the running time by at most a polynomial factor (the exact factor depending on the model of computation), and so the new machine is also in ZPP. The new machine is also guaranteed to always halt. So bounded-ZPP is the same class as ZPP.

> **Comments:**
> **username_0**: Thank you. What if one would further restrict ZPP, requiring the PTM to halt in polynomial time? (Does it equal ZPP or P? Or is it a complexity class in its own right?)  
> **username_1**: Then you'll just get P.  
> **username_2**: @JohnSmith If the machine has to halt in polynomial time, and cannot make an error, it is effectively a deterministic polynomial-time machine. Thus, your class equals P.  

---

