A note on VNP-completeness and border complexity

Ikenmeyer, Christian and Sanyal, Abhiroop (2022) A note on VNP-completeness and border complexity. INFORMATION PROCESSING LETTERS, 176. p. 106243.

Text
2102.07173v2.pdf - Submitted version
Download (472kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ipl.2021.106243

Abstract

In 1979 Valiant introduced the complexity class VNP of p-definable families of polynomials, he defined the reduction notion known as p-projection and he proved that the permanent polynomial and the Hamiltonian cycle polynomial are VNP-complete under p-projections. In 2001 Mulmuley and Sohoni (and independently B\"urgisser) introduced the notion of border complexity to the study of the algebraic complexity of polynomials. In this algebraic machine model, instead of insisting on exact computation, approximations are allowed. This gives VNP the structure of a topological space. In this short note we study the set VNPC of VNP-complete polynomials. We show that the complement VNP \ VNPC lies dense in VNP. Quite surprisingly, we also prove that VNPC lies dense in VNP. We prove analogous statements for the complexity classes VF, VBP, and VP. The density of VNP \ VNPC holds for several different reduction notions: p-projections, border p-projections, c-reductions, and border c-reductions. We compare the relationship of the completeness notions under these reductions and separate most of the corresponding sets. Border reduction notions were introduced by Bringmann, Ikenmeyer, and Zuiddam (JACM 2018). Our paper is the first structured study of border reduction notions.

Item Type:	Article
Additional Information:	Theorem 1 has been strengthened. The topology has been adjusted. Section 7 is new
Uncontrolled Keywords:	Theory of computation, Computational complexity, Algebraic complexity theory, Border complexity, Reductions
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	09 Jul 2021 07:16
Last Modified:	18 Jan 2023 21:36
DOI:	10.1016/j.ipl.2021.106243
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3129307