2012/10/29 by Nicolas de Rugy-Altherre, de Rugy-Altherre, Nicolas
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1210.7641
openalex publication_date 2012/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the present paper we show a dichotomy theorem for the complexity of polynomial evaluation. We associate to each graph H a polynomial that encodes all graphs of a fixed size homomorphic to H. We show that this family is computable by arithmetic circuits in constant depth if H has a loop or no edge and that it is hard otherwise (i.e., complete for VNP, the arithmetic class related to #P). We also demonstrate the hardness over the rational field of cut eliminator, a polynomial defined by Bürgisser which is known to be neither VP nor VNP-complete in the field of two elements, if VP is not equal to VNP (VP is the class of polynomials computable by arithmetic circuit of polynomial size).