The basic thrust of the author’s research is an application of the classical Turing-machine based theory of computation to the classical problems of numerical analysis. This paper deals with the polynomial time computability of Ordinary Differential Equations (ODEs). For a continuous real-valued function f on [ 0 , 1 ] × [ − 1 , 1 ], let y denote a solution of the ODE y′ ( x ) = f ( x , y ( x ) ) ( 0 < x < 1 ) with initial condition y ( 0 ) = 0. The author is interested in the computational complexity of y relative to that of f. Here, the underlying model of computation is based on oracle Turing machines.

The author first asks whether polynomial time computability of f implies polynomial time computability of y. He shows that this is not the case; there exists a polynomial time computable f such that for any &dgr; > 0, the ODE (with initial condition y ( 0 ) = 0 ) has no computable solution on [ 0 , &dgr; ). He next asks what happens when the problem has a unique solution y. He shows that for any recursive function &phgr;, there is a polynomial time computable f such that the ODE (with initial condition y ( 0 ) = 0 ) has a unique solution on [ 0 , 1 ], yet y is not computable by any oracle TM operating in time &phgr;.

Next, we impose the additional hypothesis that f is Lipschitz continuous. Let P _f and PSPACE _f denote the classes of all functions from { 0 , 1 }* into { 0 , 1 }* which are polynomial time (respectively, space) computable. It follows easily from known results that P _f = PSPACE _f ⟹ polynomial time computability of f under these new hypotheses implies polynomial time computability of y ⟹ P _f = # P _f. In view of the difficulty of resolving these two major open problems, the author replaces this quest by a weaker one that is perhaps more realistic. He asks whether there exists a natural complexity class F between # P _f and PSPACE P _f such that polynomial time computability of f (which is Lipschitz and for which the existence and uniqueness of the solution y of the ODE initial value problem is guaranteed) implies that of y. The author answers a still weaker variant of this question. He weakens the requirement of a Lipschitz condition on f to the requirement that f satisfy a “right Lipschitz condition” on a special subset E. He then shows that (under the new hypotheses) the polynomial time computability of f always implies that of y iff P = PSPACE. As a corollary, he also shows that if P ≠ PSPACE, then (for some type of functions f) Euler’s method is at least as efficient as any other method (to within a polynomial factor).