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

Univ Paris Diderot, Sorbonne Paris Cité

IMJ-PRG, UMR 7586 CNRS

Sorbonne Université

UPMC Univ Paris 06, F-75013, Paris, France.

Meena Mahajan

The Institute of Mathematical Sciences,

Chennai 600113, India

`meena AT imsc DOT res DOT india`

Guillaume Malod

Univ Paris Diderot, Sorbonne Paris Cité

IMJ-PRG, UMR 7586 CNRS

Sorbonne Université

UPMC Univ Paris 06, F-75013, Paris, France.

`malod AT math DOT univ-paris-diderot DOT fr `

Nicolas de Rugy-Altherre

Univ Paris Diderot, Sorbonne Paris Cité

IMJ-PRG, UMR 7586 CNRS

Sorbonne Université

UPMC Univ Paris 06, F-75013, Paris, France.

`nderugy AT math DOT univ-paris-diderot DOT fr `

Nitin Saurabh

The Institute of Mathematical Sciences,

Chennai 600113, India

`nitin AT imsc DOT res DOT in`

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.

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

Licensed under a Creative Commons Attribution License

Volume 2016, Article 2 Article 4

Volume 2016 Published articles