...\author

Supported in part by NSF under grant CCR-9424164. Support was also provided by the University of North Carolina at Greensboro in the form of research leave.

...\author

Department of Mathematical Sciences, University of North Carolina at Greensboro, Greensboro, NC 27412, USA. E-mail: wang@uncg.edu.

...

Levin [Lev86] used to denote a distribution function and used to denote its density. Since almost all of our statements can be stated directly in terms of probability distributions, denoting a probability distribution by without a prime seems more convenient. The notations and were first used in [Gur91a].

...

To see the equivalence, assume that . Let . Then, for all , , and so . The other direction is straightforward by a simple application of Markov's inequality.

...

Actually, we are dealing with the conditional probability distribution with . Since and is a positive constant, this is equivalent to using in the inequality.

...

The converse is also true if is bounded by a polynomial in [Gur91a].

...

We may also weaken the second requirement in Definition 3.5 to require only that, for all but finitely many , either or . In this case, is uniform in the sense that if a string can be picked with a positive probability, then every string of length will have the same chance to be selected with a ``fair'' probability greater than .

...

The index here is selected uniformly as a binary string. The issue of how to select , however, is not important in obtaining the completeness result. One can use one's favorite distributions to select it, e.g., one may select states and transition functions according to different distributions.

...

To see that , it suffices to note that .

...

Note that such results are machine dependent. For example, the linear speed-up theorem that holds for multi-tape Turing machines does not hold for some other models [Jon93].

...

Note that has been used as an intermediate time bound for an alternating Turing machine, to show that nondeterministic linear time is strictly more powerful than deterministic linear time [PPST83].So it would be interesting to extend log-exp functions to include functions like .

...

Note that the complete problems for constructed in [RS93] are not with respect to length-preserving ranking functions.

...

To see this, let be restricted to deterministic machine , and let be the same as . Then, clearly, is complete in P. Also, is ap-time complete for AP with respect to p-time computable distributions [WB93a].