Feasible arithmetic computations: Valiant's hypothesis

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

Joachim von zur Gathen

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/s0747-7171(87)80063-9

zbMATH Keywords

straight-line programcomplexity classes of polynomials over a fieldP\(\neq NP\) conjectureVaillant's hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items

Fast computation of discrete invariants associated to a differential rational mapping, Some complete and intermediate polynomials in algebraic complexity theory, Improved construction for universality of determinant and permanent, Permanent and determinant, Lower bounds for the circuit size of partially homogeneous polynomials, On enumerating monomials and other combinatorial structures by polynomial interpolation, On the Expressive Power of Read-Once Determinants, Lower bounds for the determinantal complexity of explicit low degree polynomials, Cook's versus Valiant's hypothesis, CATEGORICAL COMPLEXITY, Characterizing Valiant's algebraic complexity classes, Improved bounds for reduction to depth 4 and depth 3, On Hard Instances of Non-Commutative Permanent, Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes, Planar acyclic computation, On hard instances of non-commutative permanent, Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials, Monomials in arithmetic circuits: complete problems in the counting hierarchy

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