We study the problem of generating monomials of a polynomial in the context of enumeration complexity. We present two new algorithms for restricted classes of polynomials, which have a good delay between two generated monomials and the same global running time as the classical ones. Moreover they are simple to describe, use small evaluation points and one of them is parallelizable. We introduce TotalPP, IncPP and DelayPP, which are probabilistic counterparts of the most common classes for enumeration problems, hoping that randomization will be a tool as strong for enumeration as it is for decision. Our interpolation algorithms prove that a few interesting problems are in these classes like the enumeration of the spanning hypertrees of a 3-uniform hypergraph. Finally we give a method to interpolate degree 2 polynomials with an acceptable (incremental) delay. We also prove that finding a specified monomial in a degree 2 polynomial is hard unless RP = NP. It suggests that there is no algorithm with a delay as good (polynomial) as the one we achieve for multilinear polynomials.
展开▼
