Homomorphism polynomials complete for VP

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

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

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
• Some complete and intermediate polynomials in algebraic complexity theory
• Some complete and intermediate polynomials in algebraic complexity theory

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 (5)

• On the closures of monotone algebraic classes and variants of the determinant
• On the closures of monotone algebraic classes and variants of the determinant
• Title not available (Why is that?)
• Some complete and intermediate polynomials in algebraic complexity theory
• Monotone arithmetic complexity of graph 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)