The complexity theory has evolved for the last three decades,
and several key concepts turn out
to be useful in classifying decision problems into ``easy'' class
and ``hard'' class. In particular, it is almost always the case that
if a problem is in the intersection of classes NP and co-NP, then
it is in P or equivalently polynomially solvable. Among the few problems
that resist this deduction is the composite integer problem to decide
whether a given binary integer is composite or not.
Considering that a decision problem must be in both NP and co-NP
in order to be polynomially solvable, NP 
co-NP represents
the ``easy'' class quite accurately.
One drawback of the well-accepted theory is that it lacks notions that can be used to classify a much larger class of mathematical problems than the class of decision problems. In particular, neither NP, co-NP nor P can deal with problems with large output. One typical example is the enumeration problem which is to generate all objects satisfying a given set of conditions. The spanning tree enumeration problem is to generate all spanning trees of a given undirected graph as input. The output of such a problem is large, that is, not bounded above by any polynomial in the size of input.
The purpose to this note is to introduce the new notions of ENP and EP
that extend the classes NP co-NP and P, respectively. It is strongly
hoped that the natural analog of the deduction above works in this setting
as well, that is, if a problem is in ENP, then it is in EP. Complexity
analysis of various enumeration problems will be subject of on-going
research by the author, and will be published in near future.
Valiant [Val79] used the expression ``complexity of enumeration"
to define the classes #P and #P-complete.
These notions are different from
ours since Valiant's notion is to classify the complexity of
COUNTING the number of objects, while
we are interested in that of GENERATING all objects.
The size of output in the case of counting is often bounded
by a polynomial in the input size, even when the size of the set of all objects
is not polynomially bounded. For example, the case of spanning trees, the number of
spanning trees of a graph with n vertices and m edges
is bounded above by 
whose size is 
.
Thus it is extremely important to distinguish an enumeration problem
from the associated counting problem. We use the term ``enumeration''
to mean to generate all objects explicitly.
It should be noted that we do not use here the Turing machine to define the new classes, since it might hide the most important aspects of the new notion. It is quite simple to deduce the corresponding (possibly slightly stronger) notions with the Turing machine.