the paper you cite by Ercsey-Ravasz, Toroczkai is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical physics and spin glasses was uncovered mainly via "phase transitions" in the mid 1990s and that has led to a large body of work, see Gogioso for a 56p survey. the phase transition coincides with what is known as "the constrainedness knife edge" in . the exact same transition point does turn up in very theoretical analyses of computational complexity/ hardness eg  that also relate to early studies of transition point behavior in clique problems by Erdos.  is a survey/ video lecture on phase transitions and computational complexity by Moshe Vardi.  are overviews of phase transition behavior across NP complete problems by Moore, Walsh.
then there is scattered but maybe increasing study of the diverse connections of dynamical systems with computational complexity and hardness in a variety of contexts. there is a general connection found in  possibly explaining some of the underlying reasons for frequent "overlap". refs  are diverse but show a reoccuring theme/ crosscutting appearance between NP complete problems and various dynamical systems. in these papers there is some concept/ examples of a hybrid link between discrete and continuous systems.
chaotic behavior in NP complete systems is analyzed in .
A somewhat similar ref to Ercsey-Ravasz/ Toroczkai in the area of quantum algorithms in that the dynamical system is found to run "apparently" in P-time 
In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.
 Aspects of Statistical Physics in Computational Complexity / Gogioso
 The constrainedness knife edge / Toby Walsh
 The Monotone Complexity of k-Clique on Random Graphs / Rossman
 Phase transitions and computational complexity / Moshe Vardi
 Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore
 Phase transition behavior / Walsh
 Determining dynamical equations is hard / Cubitt, Eisert, Wolf
 The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems / Just
 Predecessor and Permutation Existence Problems for Sequential Dynamical Systems / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates)
 A Dynamical Systems Approach to Weighted Graph Matching / Zavlanos, Pappas
 On chaotic behaviour of some np-complete problems / Perl
 New quantum algorithm for studying NP-complete problems / Ohya, Volovich