# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Completeness and reduction in algebraic complexity theory. (English) Zbl 0948.68082
Algorithms and Computation in Mathematics. 7. Berlin: Springer. xii, 168 p. DM 129.00; £ 44.50; öS 942.00; sFr 117.50; $74.95 (2000). 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}\ne \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}\ne \text{NP/poly}$and the generalized Riemann hypothesis holds, then$\text{VP}\ne \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}\ne \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}\ne \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.

##### MSC:
 68Q15 Complexity classes of computation 68-02 Research monographs (computer science)