The Computational Complexity of Algebraic and Numeric Problems

a-indep a₁ a₂ active operations algebraically dependent algorithm apply arithmetic operations assume asymptotically asymptotically optimal b₁ bilinear forms Borodin c₁ C₂ coefficients COROLLARY defined DEFINITION denote dimension division elements Euclidean domain f₁ follows given FU graph hence Hopcroft Horner's rule indeterminate induction integer interpolation inversion irreducible iteration L₁ L₂ Lemma linear program linear subspace linearly independent log² m₁ matrix multiplication method modular multi nomials nonscalar multiplications nonscalar operations nth degree polynomial number of arithmetics O(log O(n log opera operations are required optimal P₁ P₂ parallel steps Paterson points polynomial evaluation polynomial of degree power series preconditioning problem processors Proof puting q₁ R₁ R₂ rational function recursion requires at least root of unity S₁ scalar multiplications Section single precision Strassen Suppose technique Theorem tion unbounded parallelism Winograd y₁ zeros