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 greedy algorithms which approximate SCS and LCS with expected additive errors @math and @math for any @math , respectively. Incidentally, our analyses also provide tight upper and lower bounds on the expected LCS and SCS lengths for a set of random sequences, solving a generalization of another well-known open question on the expected LCS length for two random sequences [K. Alexander, The rate of convergence of the mean length of the longest common subsequence, 1992, manuscript],[V. Chvatal and D. Sankoff, J. Appl. Probab., 12 (1975), pp. 306-315], [D. Sankoff and J. Kruskall, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983]. We introduce a new approach to isolate the real roots of a square-free polynomial @math with real coefficients. It is assumed that each coefficient of @math can be approximated to any specified error bound. The presented method is exact, complete and deterministic. Due to its similarities to the Descartes method, we also consider it practical and easy to implement. Compared to previous approaches, our new method achieves a significantly better bit complexity. It is further shown that the hardness of isolating the real roots of @math is exclusively determined by the geometry of the roots and not by the complexity or the size of the coefficients. For the special case where @math has integer coefficients of maximal bitsize @math , our bound on the bit complexity writes as @math which improves the best bounds known for existing practical algorithms by a factor of @math . The crucial idea underlying the new approach is to run an approximate version of the Descartes method, where, in each subdivision step, we only consider approximations of the intermediate results to a certain precision. We give an upper bound on the maximal precision that is needed for isolating the roots of @math . For integer polynomials, this bound is by a factor @math lower than that of the precision needed when using exact arithmetic explaining the improved bound on the bit complexity. The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of @math on the smoothed running-time of the k-means method, where n is the number of data points and @math is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice. We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in @math and @math . Second, we prove an upper bound of @math , where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for @math . Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances. We present new approximation algorithms for the @math -median and @math -means clustering problems. To this end, we obtain small coresets for @math -median and @math -means clustering in general metric spaces and in Euclidean spaces. In @math , these coresets are of size with polynomial dependency on the dimension @math . This leads to @math -approximation algorithms to the optimal @math -median and @math -means clustering in @math , with running time @math , where @math is the number of points. This improves over previous results. We use those coresets to maintain a @math -approximate @math -median and @math -means clustering of a stream of points in @math , using @math space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.