Feasible arithmetic computations: Valiant's hypothesis
type: Item
instance of: scholarly article
title: Feasible arithmetic computations: Valiant's hypothesis
zbMATH Open document ID: 0662.68033
DOI: 10.1016/S0747-7171(87)80063-9
author: Joachim von zur Gathen
published in: Journal of Symbolic Computation
publication date: 1987-01-01T00:00:00Z
review text: This paper gives an introduction to complexity classes of polynomials over a field. The basic notion is a straight-line program over a field F. Such a program does not contain loops. It consists of steps which are either additions, subtractions, multiplications or divisions over F, with results of earlier lines, or an input of an element of F. Such algorithms give rise to complexity classes of polynomials that are called p- computable, p-expressible, qp-computable, qp-expressible or p-definable. The definitions of these classes are too complex to put them here. It is proven that p-expressible implies p-computable implies p-definable. Moreover it can be shown that p-computable does not imply p-expressible. Vaillant's hypothesis conjectures that p-definable is not equal to p- computable. This is a polynomial variant of the \(P\neq NP\) conjecture. A p-complete family of polynomials is a family that is the computational hardest in the class p-definable. It is shown that the permanent family, i.e., \(f_ n\) computes the general permanent of an \(n\times n\)-matrix, is p-complete.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 12E05
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 4082964
zbMATH Keywords: complexity classes of polynomials over a field
zbMATH Keywords: straight-line program
zbMATH Keywords: Vaillant's hypothesis
zbMATH Keywords: P\(\neq NP\) conjecture
MaRDI profile type: Publication
cites work: The complexity of partial derivatives
cites work: On computing the determinant in small parallel time using a small number of processors
cites work: Q3222324
cites work: Q3962468
cites work: Fast parallel matrix and GCD computations
cites work: Q4190138
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: A note on the complexity of algebraic differentiation
cites work: Q3719722
cites work: Q4138187
cites work: Fast Parallel Matrix Inversion Algorithms
cites work: Very Fast Parallel Polynomial Arithmetic
cites work: Q4198056
cites work: Irreducibility of multivariate polynomials
cites work: Q4725742
cites work: Permanent and determinant
cites work: Factoring sparse multivariate polynomials
cites work: Boolean circuits versus arithmetic circuits
cites work: Lower bounds for polynomials with algebraic coefficients
cites work: On the Parallel Evaluation of Multivariate Polynomials
cites work: Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
cites work: Q3735080
cites work: A Lower Bound for the Formula Size of Rational Functions
cites work: Q4142699
cites work: New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
cites work: The van der Waerden conjecture: Two proofs in one year
cites work: On the relation between the determinant and the permanent
cites work: Q3727384
cites work: An inequality for permanent of (0, 1)-matrices
cites work: Q5829318
cites work: New NP-hard and NP-complete polynomial and integer divisibility problems
cites work: Logarithmic Depth Circuits for Algebraic Functions
cites work: Q3851094
cites work: Q4172915
cites work: A complexity theory based on Boolean algebra
cites work: Berechnung und Programm. I
cites work: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
cites work: Q4047029
cites work: Polynomials with Rational Coefficients Which are Hard to Compute
cites work: Q3340795
cites work: Q3813775
cites work: The complexity of computing the permanent
cites work: Q3929052
cites work: Fast Parallel Computation of Polynomials Using Few Processors
full work available at URL: s0747-7171(87)80063-9
OpenAlex ID: W2064224503
description: scientific article; zbMATH DE number 4082964