Journal of Symbolic Logic 65 (4):1675-1685 (2000)
Let 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
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
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.
Every Polynomial-Time 1-Degree Collapses If and Only If P = Pspace.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
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.
An Extension of the Cobham-Semënov Theorem.Alexis Bès - 2000 - Journal of Symbolic Logic 65 (1):201-211.
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 index2009-01-28
Total downloads5 ( #582,478 of 2,143,766 )
Recent downloads (6 months)1 ( #386,855 of 2,143,766 )
How can I increase my downloads?
There are no threads in this forum
Nothing in this forum yet.