期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-25
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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
