LIPIcs.FSTTCS.2014.493.pdf
- Filesize: 0.49 MB
- 12 pages
Document
Homomorphism Polynomials Complete for VP
Authors
-
Part of:
Volume:
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-12-12
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
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.
Subject Classification
Keywords
- algebraic complexity
- graph homomorphism
- polynomials
- VP
- VNP
- completeness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317-330, 1983.
-
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.
-
P. Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer, 2000.
-
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.
-
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.
-
Arnaud Durand and Stefan Mengel. The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci., 80(1):277-296, 2014.
-
Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245-1274, 2013.
-
Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. Journal of Complexity, 24(1):16-38, 2008.
-
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.
-
Ran Raz. Elusive functions and lower bounds for arithmetic circuits. Theory of Computing, 6:135-177, 2010.
-
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.
-
Leslie G. Valiant. Completeness classes in algebra. In Symposium on Theory of Computing STOC, pages 249-261, 1979.
-
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.
-
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.