PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

summary

The gist

Dynamical systems are widely used as models of computation and this paper proves that under suitably quantified robustness assumptions…

This episode discusses

The paper

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems · Read on arXiv

Manon BLANC

ITU i © København

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems".

Jane: Here's the gist of the paper. PSPACE-completeness of the reachability relation of robust dynamical systems proves that under suitably quantified robustness assumptions, the reachability relation for discrete-time and continuous-time robust dynamical systems becomes PSPACE-complete for both classical and second-order complexity Under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity, for an adapted notion of reduction The paper links results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity Reachability in Discrete Time The problem of reachability in discrete-time dynamical systems is well-known to be computably enumerable but not decidable in the general case, even when the underlying dynamics is computable With a proper notion of robustness, as defined in Definition 3, Reach becomes decidable For discrete-time models of computations over the reals, the most famous approaches are computable analysis based on Turing machines (TMs) and algebraic models such as the Blum Shub Smale (BSS) model The complexity of the problem crucially depends on the dynamical systems we consider Assuming f preserves the rationals (f(Q) ⊆ Q), we have Reach(x,y) c.e.-complete and Reach(x,Y) c.e.-complete Robustness and Complexity Bounds The authors define robustness by insensitivity to an arbitrarily small perturbation, where a system is robust if each of those open sets intersects the (non-perturbed) solution point The authors of

5: proved it is also possible to deal with complexity questions, and not only computability With the proper quantification over the allowed perturbation, namely the radius of the open sets (2−p(n), p a polynomial and n ∈ N related to some notion of size), they prove that Reach is in PSPACE The existing results regarding those systems are summed up here: X ⊆ R, H non-robust H robust H poly.

Tom: robust, f ∈ FPTIME Lips PSPACE-Completeness Results The main results of this paper are PSPACE-completeness over the reals results The authors prove that, with robust oracle TMs (Definition 6), and second-order reductions over real functions (Definition 10), we have the PSPACE2−≤2m-hardness of Reach, for both discrete-time (“DRRL” in Lemma 30 and Corollary 32) and continuous-time dynamics (“CRRL” in Theorem 42 and Corollary 43) With the membership results of

5, 7: , it implies that both problems are PSPACE2−≤2m-complete Algebraic Characterizations and Side Effects As a side-effect, the authors prove that we can remove the cosine as a base function from the algebra of

6: , which gives a characterisation of FPSPACE over the reals (Theorem 41) with an algebra with a smaller basis This convergence toward a minimal algebra for characterising polynomial space with ODEs is noted Continuous-Time Complexity The goal of this subsection is to extend Lemma 30.

Jane: It relies on previous results from

6: The main new results here are Lemma 35 and Theorem 42 Continuous Reach Robust Lipschitz (CRRL) is defined as the problem for a continuous-time polynomially robust dynamical system HC = (XC, gC) CRRL is PSPACE2−≤2m-hard Simulation and Reduction Techniques The Simulation Trick is used to prove the PSPACE2−hardness of this problem, reducing from DRRL The core idea of this method is, starting from a discrete dynamic, to construct a continuous ODE whose (smooth) dynamic goes through all the points of the discrete dynamic The simulation of Proposition 71 is computable in polynomial time Final Completeness Summary Having such completeness results allows us to have a better understanding of those complexity classes over the reals We now have PSPACE-completeness results for Reach Robust LDL◦light DRRL CRRL-Completeness PSPACE (Cor.

Tom: 25) PSPACE2 (Cor.

Paper summary: Tom: To get into the specifics of "PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems", this paper focuses on discrete-time and continuous-time robust dynamical systems over the reals >

Jane: It claims that under certain quantified robustness assumptions, reachability for these systems becomes PSPACE-complete in terms of computable analysis >

Lu: The core thesis is that they prove the necessary complexity lower bound, showing it's not just decidable but hard to solve within PSPACE2 minus two m hardness >

Meng: So, what makes it PSPACE2 minus two m? Is that related to how they define the oracle Turing machines or the reduction used >

Tom: They use robust oracle TMs, as defined in Definition six and second-order reductions over real functions as defined in Definition ten > <ref:2610.26206#pg3,Definition 6, and second-order reductions over real functions>

Jane: That links dynamical systems directly to second-order complexity classes over the reals, which is a pretty deep connection for this area of study >

Lalam: It connects results from dynamical systems and complexity over the reals, including models of computable analysis and second-order complexity >

Conclusion: Tom: So what's the big picture here? The paper shows that reachability in these robust systems isn't just a simple decidable problem; it sits at a high level of computational difficulty >

Jane: It means if you are working with continuous or discrete dynamics that have this level of robustness, you can expect the problem to require polynomial space resources to solve >

Lu: It’s about getting a more precise description of what polynomial space means in models closer to the analogue world, which is what they aim for >

Meng: From an engineering standpoint, it tells us that we need to be very careful when we design these systems if reachability is a critical part of their operation >

Tom: And as a side effect, they managed to simplify an algebraic basis for characterizing PSPACE over the reals by removing the cosine function >

Jane: It suggests there might be simpler, more fundamental ways to characterize polynomial space using ordinary differential equations than what was previously used >

More episodes

← Home