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
is one which solves, for
,
in space
polynomial in both input size |x| and
the largest size |y| of output objects y.
Class CEP (a subclass of EP)
is in CEP if
a compact polynomial algorithm for
.