Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
A Dichotomy Theorem for Homomorphism Polynomials
verfasst von : Nicolas de Rugy-Altherre
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 edges and that it is hard otherwise (i.e., complete for VNP, the arithmetic class related to #
P
). We also demonstrate the hardness over ℚ of cut eliminator, a polynomial defined by Bürgisser which is known to be neither VP nor VNP-complete in
$\mathbb F_2$
, if VP ≠ VNP (VP is the class of polynomials computable by arithmetic circuits of polynomial size).