Journal of Symbolic Logic 65 (4):1675-1685 (2000)
AbstractLet f be a function from N to N that can not be computed in polynomial time, and let a be an element of a differential field K of characteristic 0. The problem of large powers is the set of tuples x̄ = (x 1 ,..., x n ) of K so that x 1 = a f(n) , and the problem of large roots is the set of tuples x̄ of K so that x f(n) 1 = a. These are two examples of problems that the use of derivation does not allow to solve quicker. We show that the problem of large roots is not polynomial for the differential field K, even if we use a polynomial number of parameters, and that the problem of large powers is not polynomial for the differential field K, even for non-uniform complexity. The proofs use the polynomial stability (i.e., the elimination of parameters) of field of characteristic 0, shown by L. Blum. F. Cucker. M. Shub and S. Smale, and the reduction lemma, that transforms a differential polynomial in variables x̄ into a polynomial in variables x̄. and their derivatives
Similar books and articles
On Different Proof-Search Strategies for Orthologic.Uwe Egly & Hans Tompits - 2003 - Studia Logica 73 (1):131 - 152.
On Polynomial Time Computation Over Unordered Structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Numerically Solving Physiological Models Based on a Polynomial Approach.F. Tudoret, A. Bardou & G. Carrault - 2001 - Acta Biotheoretica 49 (4):247-260.
Proving Theorems of the Second Order Lambek Calculus in Polynomial Time.Erik Aarts - 1994 - Studia Logica 53 (3):373 - 387.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Added to PP
Historical graph of downloads