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.
In @cite_12 we have shown that a different kind of restriction on allows for a finer complexity analysis over unbounded time domain. More precisely, if @math is a polynomial (i.e. @math is solution of ) then @math can be computed in time polynomial in @math , in the accuracy of the result, and in @math . More precisely, its running time is polynomial in the product @math (and the size of the coefficients). However this result is not satisfactory for several reasons. First, and we insist on this point, it requires some , i.e. a bound on @math , which is only semicomputable in general. This means the algorithm in @cite_12 is unusable without some knowledge of the result. Second, this result is in some sense a worst-case scenario: if @math spikes'' and then becomes really small, then the resulting complexity will be high. Here we present an algorithm where @math can be computed in time polynomial in @math , which is related to the length'' of the solution curve (see Definition ). The following examples illustrate that the difference in complexity can be huge.
@cite_12
2053544268
The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) are two well-known NP -hard problems that have applications in many areas including computational molecular biology, data compression, robot motion planning and scheduling, text editing, etc. A lot of fruitless effort has been spent in searching for good approximation algorithms for these problems. In this paper, we show that these problems are inherently hard to approximate in the worst case. In particular, we prove that (i) SCS does not have a polynomial time linear approximation algorithm, unless P = NP ; (ii) There exists a constant @math such that, if SCS has a polynomial time approximation algorithm with ratio @math , where @math is the number of input sequences, then NP is contained in DTIME @math ; (iii) There exists a constant @math such that, if LCS has a polynomial time approximation algorithm with performance ratio @math , then P = NP . The proofs utilize the recent results of [Proc. 23rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23] on the complexity of approximation problems. In the second part of the paper, we introduce a new method for analyzing the average-case performance of algorithms for sequences, based on Kolmogorov complexity. Despite the above nonapproximability results, we show that near optimal solutions for both SCS and LCS can be found on the average. More precisely, consider a fixed alphabet @math and suppose that the input sequences are generated randomly according to the uniform probability distribution and are of the same length @math . Moreover, assume that the number of input sequences is polynomial in @math . Then, there are simple