next up previous
Next: Smallest space complexity of Up: Note on new complexity Previous: Classify ``easy'' enumeration problems

``Probably-easy'' enumeration problems?

Class ENP (an extension of class NP tex2html_wrap_inline108 coNP)

tex2html_wrap_inline142 is in ENP if tex2html_wrap_inline166 , tex2html_wrap_inline188 (certificate) with which the correctness of output can be verified in time polynomial in both the input size |x| and the output size.


Proposition. EP tex2html_wrap_inline192 ENP.

Conjecture. EP tex2html_wrap_inline194 ENP.

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