Cook's versus Valiant's hypothesis
type: Item
instance of: scholarly article
title: Cook's versus Valiant's hypothesis
zbMATH Open document ID: 0943.68070
DOI: 10.1016/S0304-3975(99)00183-8
author: Peter Bürgisser
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
review text: Valiant developed a nonuniform algebraic analogue of the theory of NP-completeness for computations with polynomials over a field \(k\) in [\textit{L. G. Valiant}, Proceedings of the 11th ACM STOC, 1979, pp. 249-261; Logic and algorithmic, int. Symp., Zürich 1980, Monogr. L'Enseign. Math. 30, 365-380 (1982; Zbl 0474.68062)]. This theory centers around his hypothesis VP\(_{k}\neq\)VNP\(_{k}\), the analogue of Cook's hypothesis P\(\neq\)NP. We identify the Boolean parts of Valiant's algebraic complexity classes VP\(_{k}\) and VNP\(_{k}\) as familiar nonuniform complexity classes. As a consequence, we obtain rather strong evidence for Valiant's hypothesis: if it were wrong, then the nonuniform versions of NC and PH would be equal. In particular, the polynomial hierarchy would collapse to the second level. We show this for fields of characteristic zero and finite fields; in the first case we assume a generalized Riemann hypothesis. The crucial step in our proof is the elimination of constants in \(k\), which relies on a recent method proposed by \textit{P. Koiran} [J. Complexity 12, No. 4, 273-286, Art. No. 0019 (1996; Zbl 0862.68053)].
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1454435
zbMATH Keywords: algebraic complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: elimination of constants
zbMATH Keywords: reduction modulo primes
MaRDI profile type: Publication
cites work: Arithmetization: A new method in structural complexity theory
cites work: Q4717931
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Completeness and reduction in algebraic complexity theory
cites work: Q3836529
cites work: Q4331740
cites work: The complexity of theorem-proving procedures
cites work: On the Power of Real Turing Machines over Binary Inputs
cites work: Feasible arithmetic computations: Valiant's hypothesis
cites work: Q4850731
cites work: Q4385525
cites work: Q3957950
cites work: Q4385522
cites work: Hilbert's Nullstellensatz is in the polynomial hierarchy
cites work: Q4297380
cites work: Q4714022
cites work: Q4135671
cites work: Number fields
cites work: Q3963114
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Q3929052
cites work: Fast Parallel Computation of Polynomials Using Few Processors
cites work: NP is as easy as detecting unique solutions
cites work: Q4773795
cites work: Finding the number of factors of a polynomial
description: scientific article; zbMATH DE number 1454435