ex-hota911 / la2011winter Goto Github PK

it would have helped to have an intuition about the really technical parts of the paper, e.g., proofs of Theorem 2 and Lemma 10.

3. Personally, I would have written “h’(t)” in Eq. (1.1) instead of “Dh(t)” in Eq. (1.1) to make things coherent with the abstract (but I would leave the other “D” since this less usual notation is recalled afterwards).

補題4.3.の\gamma を削除

Appendixなので提出後

5. It is mentioned in Table 1.1 that if g is analytic, then the solution of the ODE is polynomial-time. But the results I know (and that seems to be the case of the references [7,9]) say that the solution is locally polynomial-time computable (in a neighborhood), with no assurance that those results can be extended over a whole compact like [0,1]. I think this should be mentioned in table 1.1, otherwise the reader might occur in error and think that the solution is polynomial-time computable for all t in [0,1].

1. I find Theorem 12 quite interesting on its own. It is a pity that this result is not mentioned in the Introduction. I do understand that the notation behind this theory takes some space to introduce, but why not state an “intuitive version” of the Theorem in the Introduction (pointing to Theorem 12 for an accurate version), or at least write something saying that Theorem 1 can be generalized to cases where g is not necessarily polynomial-time computable?

2. The results presented in the paper, as well as previous results by Kawamura or those mentioned in Ko’s book [5] are valid only for ODEs defined on compacts (typically t is restricted to the interval [0,1]). But there are many important ODEs which have their solutions defined for every t >= 0. How does the complexity of the solution of the ODE depend on t? It is natural that the higher t, the higher the resources needed to compute the solution with a given precision. But how do these resources grow with t? This problem is still PSPACE-complete? In my opinion, that would be an interesting question to study too. Restricting time to a given compact provides a good first start but, in my opinion, general results about the complexity of ODEs should also measure complexity relative to t.
   Last year a paper with some results in this direction (“Solving analytic differential equations in polynomial time over unbounded domains” by O. Bournez, D. S. Graça, and A. Pouly) was presented at this conference, but it seems that there are many questions and few answers…