Feasible arithmetic computations: Valiant's hypothesis

DOI10.1016/S0747-7171(87)80063-9zbMath0662.68033MaRDI QIDQ1114391

Joachim von zur Gathen

Publication date: 1987

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

straight-line program; complexity classes of polynomials over a field; P\(\neq NP\) conjecture; Vaillant's hypothesis

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

12E05: Polynomials in general fields (irreducibility, etc.)

Related Items

Planar acyclic computation, Improved construction for universality of determinant and permanent, Permanent and determinant, Fast computation of discrete invariants associated to a differential rational mapping, Cook's versus Valiant's hypothesis, Characterizing Valiant's algebraic complexity classes, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On the relation between the determinant and the permanent
• On computing the determinant in small parallel time using a small number of processors
• New NP-hard and NP-complete polynomial and integer divisibility problems
• Factoring sparse multivariate polynomials
• Irreducibility of multivariate polynomials
• Permanent and determinant
• Lower bounds for polynomials with algebraic coefficients
• The complexity of partial derivatives
• The van der Waerden conjecture: Two proofs in one year
• A note on the complexity of algebraic differentiation
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Berechnung und Programm. I
• Boolean circuits versus arithmetic circuits
• Fast Parallel Computation of Polynomials Using Few Processors
• Very Fast Parallel Polynomial Arithmetic
• A Lower Bound for the Formula Size of Rational Functions
• Logarithmic Depth Circuits for Algebraic Functions
• A complexity theory based on Boolean algebra
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
• Fast Parallel Matrix Inversion Algorithms
• On the Parallel Evaluation of Multivariate Polynomials
• The Parallel Evaluation of General Arithmetic Expressions
• Fast parallel matrix and GCD computations
• Polynomials with Rational Coefficients Which are Hard to Compute
• An inequality for permanent of (0, 1)-matrices