text: (L, D) сводится в среднем к (L', D') (пишется (L, D) ≤AvgP (L', D')), если существует функция f, такая, что для любого n её можно вычислить при входе x за полиномиальное от n время и (Корректность) x ∈ L тогда и только тогда, когда f(x) ∈ L' (Доминирование) Существуют многочлены p и m, такие, что для любого n и y, ∑ x : f ( x ) = y D n ( x ) ≤ p ( n ) D m ( n ) ′ ( y ) {\displaystyle \sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)} Условие доминирования приводит к идее, что если задача (L, D) сложна в среднем, то (L', D') также сложна в среднем.