Note on new complexity classes ENP, EP and CEP
- An fentesion of the classes NP co-NP and P

Komei Fukuda
Institute for Operations Research
ETH-Zentrum, CH-8092 Zurich, Switzerland
fukuda@@ifor.math.ethz.ch

June 12, 1996

• Motivation
• Examples of Enumeration Problems
  • Enumeration Problem: Acyclic Orientations
  • Enumeration Problem: Extreme Points
  • Enumeration Problem: Triangulations
• Basic Definitions
• Classify ``easy'' enumeration problems
• ``Probably-easy'' enumeration problems?
• Smallest space complexity of enumeration?
• Final Remarks
• References
• About this document ...