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

Smallest space complexity of enumeration?

Key observation. An enumeration algorithm may not have to store all output in the active memory. Some algorithm can simply dump each output object y without storing it.

This fact motivates us to define:

Compact algorithm

A compact algorithm for tex2html_wrap_inline142 is one which solves, for tex2html_wrap_inline166 , tex2html_wrap_inline142 in space polynomial in both input size |x| and the largest size |y| of output objects y.

Class CEP (a subclass of EP)

tex2html_wrap_inline142 is in CEP if tex2html_wrap_inline172 a compact polynomial algorithm for tex2html_wrap_inline142 .

tex2html_wrap218


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