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

algebraic complexitycompletenessgraph homomorphismpolynomialsVNPVP

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

• 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
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)

Cited in

(10)

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

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)