Homomorphism polynomials complete for VP

DOI10.4086/CJTCS.2016.003MaRDI QIDQ2808529zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Meena Mahajan, Nicolas De Rugy-Altherre, Nitin Saurabh, Guillaume Malod

Publication date 24 May 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2016.003

zbMATH Keywords

graph homomorphismcompletenesspolynomialsalgebraic complexityVPVNP

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Homomorphism polynomials complete for VP
• Variants of homomorphism polynomials complete for algebraic complexity classes
• Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• A dichotomy theorem for homomorphism polynomials
• Arithmetic Circuits and Polynomial Replacement Systems
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Fast Parallel Computation of Polynomials Using Few Processors

Cited in

(8)

• On the closures of monotone algebraic classes and variants of the determinant
• Variants of homomorphism polynomials complete for algebraic complexity classes
• scientific article; zbMATH DE number 1796947 (Why is no real title available?)
• On the closures of monotone algebraic classes and variants of the determinant
• Monotone arithmetic complexity of graph homomorphism polynomials
• Homomorphism polynomials complete for VP
• Boundaries of VP and VNP
• Generalized matrix completion and algebraic natural proofs

This page was built for publication: Homomorphism polynomials complete for VP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2808529)