Document Open Access Logo

Homomorphism Polynomials Complete for VP

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2014.493.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • algebraic complexity
  • graph homomorphism
  • polynomials
  • VP
  • VNP
  • completeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.

Cite As Get BibTex

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh. Homomorphism Polynomials Complete for VP. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 493-504, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.493

Author Details

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

References

  1. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317-330, 1983. Google Scholar
  2. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Counting graph homomorphisms. In Topics in Discrete Math, pages 315-371. Springer, 2006. Google Scholar
  3. P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer, 2000. Google Scholar
  4. Florent Capelli, Arnaud Durand, and Stefan Mengel. The arithmetic complexity of tensor contractions. In Symposium on Theoretical Aspects of Computer Science STACS, volume 20 of LIPIcs, pages 365-376, 2013. Google Scholar
  5. Nicolas de Rugy-Altherre. A dichotomy theorem for homomorphism polynomials. In Mathematical Foundations of Computer Science 2012, volume 7464 of LNCS, pages 308-322. Springer Berlin Heidelberg, 2012. Google Scholar
  6. Arnaud Durand and Stefan Mengel. The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci., 80(1):277-296, 2014. Google Scholar
  7. Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245-1274, 2013. Google Scholar
  8. Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. Journal of Complexity, 24(1):16-38, 2008. Google Scholar
  9. Stefan Mengel. Characterizing arithmetic circuit classes by constraint satisfaction problems. In Automata, Languages and Programming, volume 6755 of LNCS, pages 700-711. Springer Berlin Heidelberg, 2011. Google Scholar
  10. Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6:135-177, 2010. Google Scholar
  11. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. Google Scholar
  12. Leslie G. Valiant. Completeness classes in algebra. In Symposium on Theory of Computing STOC, pages 249-261, 1979. Google Scholar
  13. Leslie G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic: International Symposium in honour of Ernst Specker, volume 30, pages 365-380. Monograph. de l'Enseign. Math., 1982. Google Scholar
  14. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12(4):641-644, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact