loading...
The Complexity of Polynomials and Their Coefficient Functions
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.33Twenty-Second Annual IEEE Conference ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Guillaume Malod, Universite de Mons-Hainaut, Belgium
We study the link between the complexity of a polynomial and that of its coefficient functions. Valiant?s theory is a good setting for this, and we start by generalizing one of Valiant?s observations, showing that the class VNP is stable for coefficient functions, and that this is true of the class VP iff VP = VNP, an eventuality which would be as surprising as the equality of the classes P and NP in Boolean complexity. We extend the definition of Valiant?s classes to polynomials of unbounded degree, thus defining the classes VP_nb and VNP_nb. Over rings of positive characteristic the same kind of results hold in this case, and we also prove that VP = VNP iff VP_nb = VNP_nb. Finally, we use our extension of Valiant?s results to show that iterated partial derivatives can be efficiently computed iff VP = VNP. This is also true for the case of polynomials of unbounded degree, if the characteristic of the ring is positive.
Citation:
Guillaume Malod, "The Complexity of Polynomials and Their Coefficient Functions," ccc, pp.193-204, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.