Computer Science – Computational Complexity
Scientific paper
2010-04-18
Computer Science
Computational Complexity
Scientific paper
10.1007/978-3-642-15155-2_55
We study the problem of generating monomials of a polynomial in the context of enumeration complexity. In this setting, the complexity measure is the delay between two solutions and the total time. We present two new algorithms for restricted classes of polynomials, which have a good delay and the same global running time as the classical ones. Moreover they are simple to describe, use little evaluation points and one of them is parallelizable. We introduce three new complexity classes, 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 proves that a lot of 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 a 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.
No associations
LandOfFree
Enumeration of the Monomials of a Polynomial and Related Complexity Classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Enumeration of the Monomials of a Polynomial and Related Complexity Classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumeration of the Monomials of a Polynomial and Related Complexity Classes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-376694