Levin [Lev86] started with the following definition to measure average time efficiency.
This definition
is robust and machine independent. Also, if a function is
an expected polynomial over distribution 
, then it is polynomial
on -average.
The reader is referred to
[Gur89]
[Gur91]
[Ven91]
[Wan96]
for motivation and justification of this definition.
A problem is solvable in average polynomial time with respect to
distribution if it can be
solved by a deterministic
algorithm whose running time is polynomial
on -average. A problem with an associated probability distribution
is called a distributional problem.
