Le problème Des granDes puissances et celui Des granDes racines
Journal of Symbolic Logic 65 (4):1675-1685 (2000)
| Abstract | 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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesUwe Egly & Hans Tompits (2003). On Different Proof-Search Strategies for Orthologic. Studia Logica 73 (1):131 - 152.
Thomas Strahm (1997). Polynomial Time Operations in Explicit Mathematics. Journal of Symbolic Logic 62 (2):575-594.
Arnold Beckmann & Samuel R. Buss (2009). Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic. Journal of Mathematical Logic 9 (01):103-138.
Alexis Bès (2000). An Extension of the Cobham-Semënov Theorem. Journal of Symbolic Logic 65 (1):201-211.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
F. Tudoret, A. Bardou & G. Carrault (2001). Numerically Solving Physiological Models Based on a Polynomial Approach. Acta Biotheoretica 49 (4).
Stephen A. Fenner, Stuart A. Kurtz & James S. Royer (2004). Every Polynomial-Time 1-Degree Collapses If and Only If P = Pspace. Journal of Symbolic Logic 69 (3):713-741.
Andreas Blass, Yuri Gurevich & Saharon Shelah (2002). On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic 67 (3):1093-1125.
Natacha Portier (1999). Stabilité Polynômiale Des Corps Différentiels. Journal of Symbolic Logic 64 (2):803-816.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
