Next: Examples of Enumeration Problems Up: Note on new complexity Previous: Note on new complexity

# Motivation

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.

Next: Examples of Enumeration Problems Up: Note on new complexity Previous: Note on new complexity

Komei Fukuda
Wed Jun 12 17:26:21 GMT+0100 1996