6
$\begingroup$

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"?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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?) $\endgroup$
    – John Smith
    Sep 1, 2017 at 16:13
  • 1
    $\begingroup$ Then you'll just get P. $\endgroup$
    – Yuval Filmus
    Sep 1, 2017 at 19:16
  • 2
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Sep 1, 2017 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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