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:
Is there a more conventional name for bounded-ZPP?
Is bounded-ZPP = ZPP?
Is P = bounded-ZPP?
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"?