Let 
be the enumeration problem for a relation R.
Polynomial algorithm
A polynomial algorithm for
is one which solves in time
polynomial in both the input size |x| and
the output size, for 
. Note that the output size
.
Class EP (an extension of class P)
is in EP if
a polynomial algorithm for .
Complexity Map
Since any decision problem can be considered as an enumeration
problem to generate all correct answers of 1 or 0, the class
EP is a natural extension of class P.
