Completeness and reduction in algebraic complexity theory
type: Item
instance of: scholarly article
title: Completeness and reduction in algebraic complexity theory
zbMATH Open document ID: 0948.68082
author: Peter Bürgisser
published in: Algorithms and Computation in Mathematics
publication date: 2000-06-14T00:00:00Z
review text: 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 orac…
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68-02
zbMATH DE Number: 1458589
zbMATH Keywords: algebraic complexity
zbMATH Keywords: complexity classes
zbMATH Keywords: P vs. NP
zbMATH Keywords: NP-completeness
zbMATH Keywords: Valiant's classes
zbMATH Keywords: structural complexity
zbMATH Keywords: relativizations
zbMATH Keywords: permanent
zbMATH Keywords: immanants
zbMATH Keywords: representations of groups
reviewed by: Armin Hemmerling
MaRDI profile type: Publication
Recommended article: Reductions, completeness and the hardness of approximability
Recommended article: Complexity classes and completeness in algebraic geometry
Recommended article: Q3738556
Recommended article: Sufficient-completeness, ground-reducibility and their complexity
Recommended article: Algorithmic reducibilities of algebraic structures
Recommended article: Q3707409
Recommended article: Complete problems and strong polynomial reducibilities
Recommended article: Complete Problems and Strong Polynomial Reducibilities
Recommended article: Q5315662
Recommended article: COMPUTABILITY IN PARTIAL COMBINATORY ALGEBRAS
description: scientific article; zbMATH DE number 1458589