×

Continuous-time orbit problems are decidable in polynomial-time. (English) Zbl 1371.68108

Summary: We place the continuous-time orbit problem in P, sharpening the decidability result shown by E. Hainry [Lect. Notes Comput. Sci. 5028, 241–250 (2008; Zbl 1142.93314)].

MSC:

68Q25 Analysis of algorithms and problem complexity
37C75 Stability theory for smooth dynamical systems

Citations:

Zbl 1142.93314
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arvind, V.; Vijayaraghavan, T. C., The orbit problem is in the GapL hierarchy, (Hu, X.; Wang, J., COCOON. COCOON, Lect. Notes Comput. Sci., vol. 5092 (2008), Springer), 160-169 · Zbl 1148.68384
[2] Baker, A., Transcendental Number Theory (1990), Cambridge University Press · Zbl 0715.11032
[3] Bell, P. C.; Delvenne, J.-C.; Jungers, R. M.; Blondel, V. D., The continuous Skolem-Pisot problem, Theor. Comput. Sci., 411, 40-42, 3625-3634 (2010) · Zbl 1215.68106
[4] Cai, J., Computing Jordan normal forms exactly for commuting matrices in polynomial time, Int. J. Found. Comput. Sci., 5, 3/4, 293-302 (1994) · Zbl 0830.68061
[5] Chonev, V.; Ouaknine, J.; Worrell, J., The orbit problem in higher dimensions, (Boneh, D.; Rougarden, T.; Feigenbaum, J., STOC (2013), ACM), 941-950 · Zbl 1293.68139
[6] Cohen, H., A Course in Computational Algebraic Number Theory (1993), Springer-Verlag · Zbl 0786.11071
[7] Hainry, E., Reachability in linear dynamical systems, (Beckmann, A.; Dimitracopoulos, C.; Löwe, B., CiE. CiE, Lect. Notes Comput. Sci., vol. 5028 (2008), Springer), 241-250 · Zbl 1142.93314
[8] Kannan, R.; Lipton, R. J., Polynomial-time algorithm for the orbit problem, J. ACM, 33, 4, 808-821 (1986) · Zbl 1326.68162
[9] Ouaknine, J.; Worrell, J., Positivity problems for low-order linear recurrence sequences, (Chekuri, C., SODA (2014), SIAM), 366-379 · Zbl 1423.11209
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.