Probabilistic polynomial time
From CRYPTUTOR
Probabilistic polynomial time (PPT) algorithms are the class of algorithms most associated with "efficient" computation. Such algorithms can use randomness, and have running times which are generally considered "efficient" in practice.
Definition
An algorithm A is probabilistic polynomial time (PPT) if it uses randomness (i.e, flips coins) and its running time is bounded by some polynomial in the input size (or often a polynomial in a security parameter).
Note that a PPT algorithm induces a distribution of outcomes, so when considering an experiment involving a PPT algorithm, we implicitly include the randomness of the algorithm as a random variable. Sometimes we make this explicit, and interpret a PPT algorithm as a deterministic algorithm which gets its random choices as an additional input. Under this interpretation, the computation 
actually refers to the probability distribution 
, where r is the polynomial bound on the number of random bits used.
Note that for non-uniform computations, a different program may be running for each input size/security parameter. However, we still insist that a single polynomial bound the running times of all of the programs.
Motivation
The definition of PPT computation allows for running times of any polynomial, even ones which are not very "efficient" in practice (say, 
). It also excludes running times that are "efficient" in practice (say, 
). However, PPT computation has the following useful characteristics:
- It is robust. That is, the composition of a polynomial number of PPT algorithms remains PPT.
- It encompasses the vast majority of "efficient" running times which occur in practice.
- On the other hand, the "inefficient" running times that are still polynomials rarely occur in practice, or in our analyses.
For these reasons, PPT computation is the most natural and useful definition of "efficiency".
