Published by the Department of Computer Science, The University of Chicago.

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.

• The article: PDF (343 KB)
• Source material: ZIP (391 KB)
• BibTeX entry for this article (332 bytes)

Submitted February 4, 2015, revised December 6, 2016, and on March 11, 2016, published March 18, 2016.

© 2016 Arnaud Durand, Meena Mahajan, Nicolas de Rugy-Altherre, and Nitin Saurabb
Licensed under a Creative Commons Attribution License

Volume 2016, Article 2

Article 4

Volume 2016

Published articles