Complexity classes and completeness in algebraic geometry (Q1740570)

This paper proposes to investigate, from an algebraic geometry point of view, questions arising in the P versus NP problem, in particular concerning complexity classes and completeness. Key concepts in computational complexity are those of reduction and completeness. The basic objects considered in this paper are sequences of projective varieties \((X_n)_{n=1}^{\infty}\). This article investigates the computational complexity of sequences of these projective varieties. This approach relies on the algebraic analogy between Valiant's theory of algebraic /arithmetic complexity classes and Boolean complexity theory. Boolean functions are replaced by polynomials over any ring, Boolean circuits are replaced by arithmetic circuits that use the multiplication and addition operations of the ring instead of the Boolean operations. A sequence \((X_n) \) is in \(\mathrm{P}_{\mathrm{proj}}\) if, for each \(n>0\), there are homogeneous polynomials whose zero set is \(X_n\) -- these are the outputs of a homogeneous arithmetic circuit of polynomially bounded size, and which have polynomially bounded degree. Sequences in \(\mathrm{NP}_{\mathrm{proj}}\) are the projections of sequences of \( X_n \subset \mathbb{P}^{n_1(n)}\times \mathbb{P}^{n_2(n)}\) in \(\mathrm{P}_{\mathrm{proj}}\), onto the first component \(\mathbb{P}^{n_1(n)}\). The main result of the paper is that there is a sequence -- called the universal circuit resultant -- which is \(\mathrm{NP}_{\mathrm{proj}}\)-complete. This is the first example of a compact family proven to be \(\mathrm{NP}_{\mathrm{proj}}\)-complete in a geometric complexity setting. The NP-completeness of the usual resultant is a long-standing open problem in Blum-Shub-Smale theory. Similar definitions are discussed for the affine varieties and projective schemes. Such an algebraic-geometry approach could not only develop new tools in algebraic geometry but also provide a framework in which the P versus NP problem is easier to progress on.