In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) y ' = p ( y ) over unbounded time domains, where p is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the "intuition" that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute.We present algorithms which numerically solve these ODEs over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time t and error bound e as input, they will output a value y ? which satisfies ? y ( t ) - y ? ? ? e . We analyze the complexity of these algorithms and show that they compute y ? in time polynomial in several quantities including the time t, the accuracy of the output e and the length of the curve y from 0 to t, assuming it exists until time t. We consider both algebraic complexity and bit complexity.
The reason to focus on the Lipschitz condition for @math seems to be fundamental when studying the computational complexity of . Indeed it is well-known (see e.g. [Theorem 7.3] Ko91 ) that if @math is not Lipschitz, then the solution of can have arbitrarily high complexity, even if @math is assumed to be polynomial-time (precision-)computable and has a unique solution. The Lipschitz condition plays an instrumental role in the complexity because it is used to derive the number of steps of the algorithm, for example in Picard-Lindel " o f theorem it is used to bound the number of iterations. It was recently shown @cite_10 , following an open problem from Ko [Section 7.2] Ko91 , that if @math is Lipschitz and polynomial-time (precision-)computable, then the solution of over @math can still be PSPACE-complete (but it was already known not to be of higher complexity @cite_8 ).
@cite_10 @cite_8
2102100313 2953245962 2053544268 2556949899
In answer to Ko's question raised in 1983, we show that an initial value problem given by a polynomial-time computable, Lipschitz continuous function can have a polynomial-space complete solution. The key insight is simple: the Lipschitz condition means that the feedback in the differential equation is weak. We define a class of polynomial-space computation tableaux with equally restricted feedback, and show that they are still polynomial-space complete. The same technique also settles Ko's two later questions on Volterra integral equations. We prove several facts concerning Lipschitz percolation, including the following. The critical probability p_L for the existence of an open Lipschitz surface in site percolation on Z^d with d 2 satisfies the improved bound p_L 1-1 [8(d-1)]. Whenever p > p_L, the height of the lowest Lipschitz surface above the origin has an exponentially decaying tail. The lowest surface is dominated stochastically by the boundary of a union of certain independent, identically distributed random subsets of Z^d. As a consequence, for p sufficiently close to 1, the connected regions of Z^ d-1 above which the surface has height 2 or more exhibit stretched-exponential tail behaviour. In this paper we prove that computing the solution of an initial-value problem y = p(y) with initial condition y(t0) = y0 ∈ Rd at time t0 + T with precision 2−μ where p is a vector of polynomials can be done in time polynomial in the value of T, μ and Y = [equation]. Contrary to existing results, our algorithm works over any bounded or unbounded domain. Furthermore, we do not assume any Lipschitz condition on the initial-value problem. We introduce the general and powerful scheme of predicting information re-use in optimization algorithms. This allows us to devise a computationally efficient algorithm for bandit convex optimization with new state-of-the-art guarantees for both Lipschitz loss functions and loss functions with Lipschitz gradients. This is the first algorithm admitting both a polynomial time complexity and a regret that is polynomial in the dimension of the action space that improves upon the original regret bound for Lipschitz loss functions, achieving a regret of @math . Our algorithm further improves upon the best existing polynomial-in-dimension bound (both computationally and in terms of regret) for loss functions with Lipschitz gradients, achieving a regret of @math .