Completeness and reduction in algebraic complexity theory (Q1567446)

This research monograph is the author's Habilitationsschrift (in mathematics, at the University of Zürich). It gives a selfcontained, uniform presentation of recent results concerning Valiant's approach to NP-completeness within the framework of algebraic complexity theory. After an introductory chapter, Valiant's algebraic model of NP-completeness is presented. Its basic complexity classes VP and VNP consist of families of polynomials (over some underlying field) which are computable resp. definable by polynomially size-bounded straight-line programs. Valiant's hypothesis says that \(\text{VP}\neq \text{VNP}\). By means of a suitable notion of reducibility, the \(p\)-projection, the notion of VNP-completeness becomes meaningful. The families of Hamilton cycle polynomials and of permanents are shown to be VNP-complete, the latter if the characteristic of the underlying field is different from two. Chapter 3 surveys VNP-completeness results for families of generating functions related to some graph properties such as perfect matchings, cliques, graph factors and connectivity. The fourth chapter dicusses first the dependency of Valiant's hypothesis on (the characteristic of) the underlying field. Then it is shown that, under certain suppositions, the nonuniform version of Cook's classical P-NP hypothesis implies Valiant's hypothesis. In particular, if \(\text{P/poly}\neq \text{NP/poly}\) and the generalized Riemann hypothesis holds, then \(\text{VP}\neq \text{VNP}\) over the field of complex numbers. The next chapter reflects on some features of structural complexity with respect to Valiant's theory. If \(\text{VP}\neq \text{VNP}\), there is a family of polynomials which is neither VNP-complete nor in VP. In contrast to the classical and the BSS setting, even a natural family with this property can be specified. Inspired by the classical result by Baker, Gill and Solovay on relativizations of P vs. NP, it is shown that VP=VNP can be ensured relative to a suitable oracle family, whereas an oracle family ensuring relativized \(\text{VP}\neq \text{VNP}\) is not yet known. Chapters 6 and 7 deal with the complexity of computing immanants. These are matrix functions generalizing both the permanent and the determinant. A fast algorithm to evaluate irreducible rational matrix representations of general linear groups, as well as a related lower bound are provided. An algorithm to evaluate immanants, faster than the previously known ones, is deduced. On the other hand, the problem of evaluating certain immanants is shown to be VNP-complete. The final chapter deals with techniques for proving that certain families are not \(p\)-definable and applies them in order to obtain separation results between a class VQP and VP resp. VNP. Moreover, relationships between Valiant's P vs. NP and the related problem within the BSS setting are discussed. The book is selfcontained and written in a clear but concise style. Several open problems and some conjectures are stated and discussed.