next up previous
Next: ``Probably-easy'' enumeration problems? Up: Note on new complexity Previous: Basic Definitions

Classify ``easy'' enumeration problems

Let tex2html_wrap_inline142 be the enumeration problem for a relation R.

Polynomial algorithm

A polynomial algorithm for tex2html_wrap_inline142 is one which solves tex2html_wrap_inline142 in time polynomial in both the input size |x| and the output size, for tex2html_wrap_inline166 . Note that the output size tex2html_wrap_inline168 .

Class EP (an extension of class P)

tex2html_wrap_inline142 is in EP if tex2html_wrap_inline172 a polynomial algorithm for tex2html_wrap_inline142 .

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. tex2html_wrap180

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