Homomorphism polynomials complete for VP

DOI10.4086/CJTCS.2016.003zbMATH Open1356.68080OpenAlexW4243387057MaRDI QIDQ2808529FDOQ2808529

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)

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

Recommendations

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

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)

Cites Work

• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Fast Parallel Computation of Polynomials Using Few Processors
• Title not available (Why is that?)
• A dichotomy theorem for homomorphism polynomials
• Arithmetic Circuits and Polynomial Replacement Systems

Cited In (8)

• On the closures of monotone algebraic classes and variants of the determinant
• Variants of homomorphism polynomials complete for algebraic complexity classes
• On the closures of monotone algebraic classes and variants of the determinant
• Title not available (Why is that?)
• 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)