Title: Enumeration Complexity and Geometric Combinatorics

Complexity theory has evolved for the last three decades, and several key concepts such as classes P, NP and co-NP turned out to be useful in classifying ``easy'' and ``hard'' decision problems. 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. In this talk we introduce new complexity classes ENP and EP that extend the classes NP $\cap$ co-NP and P, respectively, and we evaluate the hardness of several enumeration problems in polyhedral geometry. Among others, the vertex and the face enumeration in convex polyhedra, the triangulation enumeration, the hyperplane enumeration for a point set, and the tope enumeration for an arrangement will be discussed. We show that understanding combinatorics of associated geometric objects is extremely important and often essential for evaluating the hardness of each enumeration problem and for designing an efficient algorithm.