Research topic:

Constraint satisfaction problems (such as Boolean satisfiability) constitute one of the hardest classes of optimization problems with many applications in technology and industry. Understanding why these problems are hard is crucially important for the development of efficient algorithms. Recently we provided an exact mapping of Boolean satisfiability (k-SAT) into a deterministic continuous-time dynamical system (CTDS) with a unique correspondence between its set of attractors and the k-SAT solutions. We have shown that optimization hardness is fundamentally equivalent to the phenomenon of chaos and turbulence: after a critical constraint density is reached, the trajectories become transiently chaotic before finding the solutions, signaling the appearance of optimization hardness. In this project we explore this revolutionary new connection between traditionally separate fields. Our main objective is to analyze optimization hardness in constraint satisfaction using nonlinear dynamical systems theory. However, Boolean satisfiability being an NP-complete problem it has applications in almost every field of science and industry, this way our methods can be applied in many different research domains.

Aims:

Aim I: Understanding optimization hardness by studying chaotic properties of the CTDS.

A: Studying the chaotic phase transition appearing in NP-complete problems.

B: Studying the chaotic behavior of locked occupation problems, these being considered the hardest class of constraint satisfaction problems.

C: Distinguishing hard-SAT formulas characterized by long chaotic transients from permanently chaotic UNSAT formulas.

Aim II: Developing a Cellular Nonlinear Network (CNN) model for solving satisfiability problems.

A: Developing a Cellular Neural Network model for solving SAT problems.

B: Studying the effect of noise on these analog algorithms.

Progress:

Phase I (2011 October-December): Budget: 50,040 RON

- Aim IIA has been started: the mathematical CNN model has been developed

Report I

Phase II (2012): Budget: 273,480 RON

- Aim IA has been started: first observations have shown that the chaotic phase transition appears in SAT problems at a relatively small constraint density.

- Aim IIA has been completed: the properties of the CNN model has been studied both mathematically and with simulations; Its efficiency has been tested.

- Aim IB has been completed: the Sudoku game was studied as a well known example of locked occupation problems. Its transient chaotic properties were used to develop a hardness measure for the puzzles.

Report II

Phase III (2013): Budget: 348,480 RON

- Aim IA has continued: many time consuming simulations had to be implemented.

- Aim IIB has been started: the effects of noise were studied on the dynamics by simulating stochastic differential equations. Both the original and the CNN system was shown to be robust to white and coloured noise.

Report III

Phase IV (2014 January-September): Budget: 248,000 RON

- Aim IA has been completed: the appearance of chaos has been more deeply understood and explained. Results are prepared to eb published.

- Aim IC has been completed: an algorithm was developed and tested for solving the max-SAT problem (identifying the maximum number of satisfiable constraints in UNSAT problems).

- Aim IIB has been completed: the results related to noise effects were published.

Final Sintetic Report

Extra research activities:

Besides the planned activities the group had the opportunity to participate in several international research collaborations which resulted in excellent publications (Science, Nature Communications etc., see publication list).

ISI Journal articles published during the project:

- R. Sumi, B. Molnar, M. Ercsey-Ravasz, "Robust optimization with transiently chaotic dynamical systems", European Physics Letters, 106, 40002 (2014).

- Y. Ren, M. Ercsey-Ravasz, P. Wang, M.C. Gonzalez, Z. Toroczkai, "Modelling roadway network traffic using a radiation model based on temporal ranges", Nature Communications, 5, 5347 (2014)

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", Science, 342, 1238406, 2013 doi:10.1126/science.1238406

- M. Ercsey-Ravasz, Z. Toroczkai, "The Chaos Within Sudoku", Nature Scientific Reports 2, 755 (2012) doi:10.1038/srep00725

- M. Ercsey-Ravasz, R. Lichtenwalter, N.W. Chawla, Z. Toroczkai, "Range-limited Centrality Measures in Non-weighted and Weighted Complex Networks, Physical Review E 85, 066103 (2012). arxiv:1111.5382

- M. Ercsey-Ravasz, Z. Toroczkai, Z. Lakner, J. Baranyi, "Complexity of the International Agro-Food Trade Network", PLoS ONE 7(5), e37810 (2012). doi:10.1371/journal.pone.0037810

ISI Conference Proceedings:

- B. Molnár, M. Ercsey-Ravasz, "Analog dynamics for solving max-SAT problems", Proceedings of CNNA 2014, Notre Dame, IN, USA (2014)

- B. Molnár, R. Sumi, M. Ercsey-Ravasz, "A CNN SAT-solver robust to noise", Proceedings of CNNA 2014, Notre Dame, IN, USA (2014)

- K. Knoblauch, M. Ercsey-Ravasz, H. Kennedy, Z. Toroczkai, “The Brain in Space”, Proc. of IPSEN, Paris, May (2014).

- B. Molnár, M. Ercsey-Ravasz, Z. Toroczkai, "Continuous-time Neural Networks Without Local Traps for Solving Boolean Satisfiability", Proceedings of CNNA 2012, p. 4012, Torino, Italy (2012)

Book chapters:

- M. Ercsey-Ravasz, Z. Toroczkai, "Dontesek fizikaja es rejtvenyek kaosza" ("Physics of decision making and chaos of puzzles") in A fizika, matematika es muveszet talalkozasa az oktatasban, kutatasban (Physics, mathematics and arts in education and research), Ed.: A. Juhasz, T. Tel, Publisher: Science Department of the Eotvos Lorand University, Hungary, 2013.

Other publications:

- M. Ercsey-Ravasz, Z. Toroczkai, "A donteshozatal es a Sudoku kaosza" ("The Chaos Within Sudoku and Decision Making"), Termeszet Vilaga (World of Nature), invited paper in the special issue "Kaosz, Kornyezet, Komplexitas" ("Chaos, Environment, Complexity"), Budapest, Hungary, p. 122, 2013

Previous publications relevant to the project:

- M. Ercsey-Ravasz, Z. Toroczkai, "Optimization Hardness as Transient Chaos in an Analog Approach to Constraint Satisfaction", Nature Physics 7, 966 (2011) arxiv:1208.0526

Echoes in the media:

The article “The chaos within Sudoku” which appeared in Nature Scientific Reports was accessed by more than 50,000 times only in the first week and generated a large echo in the international media. Articles and comments appeared in prestigiuous newspapers such as: Huffington Post , Daily Mail , Technology review , CBS news ,

The romanian news media has also published short news and comments about our results: Income Magazine , Antena 3 Ad astra , Szabadsag

Our article in PLoS One has also generated some echoes in the international media: Science Daily Wired.com

The heavily connected brain - Cortical high-density counterstream architectures

Background.The cerebral cortex is divisible into many individual areas, each exhibiting distinct connectivity profiles, architecture, and physiological characteristics. Interactions among cortical areas underlie higher sensory, motor, and cognitive functions. Graph theory provides an important framework for understanding network properties of the interareal weighted and directed connectivity matrix reported in recent studies.Density and topology of the cortical graph. Figure (Left) The 66% density of the cortical matrix (black triangle) is considerably greater than in previous reports (colored points) and is inconsistent with a small-world network. (Right) A bow-tie representation of the high-density cortical matrix. The high-efficiency cortical core has defined relations with the cortical periphery in the two fans. Advances. We derive an exponential distance rule that predicts many binary and weighted features of the cortical network, including efficiency of information transfer, the high specificity of long-distance compared to short-distance connections, wire length minimization, and the existence of a highly interconnected cortical core. We propose a bow-tie representation of the cortex, which combines these features with hierarchical processing. Outlook. The exponential distance rule has important implications for understanding scaling properties of the cortex and developing future large-scale dynamic models of the cortex.

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", Science, 342, 1238406, 2013 doi:10.1126/science.1238406

The Chaos Within Sudoku

The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle’s hardness that correlates well with human difficulty ratings. Accordingly, η=-log₁₀ (κ) can be used to define a ‘‘Richter’’-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.

M. Ercsey-Ravasz, Z. Toroczkai, Scientific Reports 2, 755 (2012) doi:10.1038/srep00725

Echoes in media: Huffington Post , Daily Mail , Technology review , CBS news , Income Magazine , Antena 3

Also see simulation movie on youtube

Turbulent Computation

Boolean satisfiability (k-SAT) is one of the most studied optimization problems, as an efficient (that is, polynomial-time) solution to k-SAT (for k > 2) implies efficient solutions to a large number of hard optimization problems. Here we propose a mapping of k-SAT into a deterministic continuous-time dynamical system with a unique correspondence between its attractors and the k-SAT solution clusters. We show that beyond a constraint density threshold, the analog trajectories become transiently chaotic, and the boundaries between the basins of attraction of the solution clusters become fractal, signalling the appearance of optimization hardness. Analytical arguments and simulations indicate that the system always finds solutions for satisfiable formulae even in the frozen regimes of random 3-SAT and of locked occupation problems (considered among the hardest algorithmic benchmarks), a property partly due to the system's hyperbolic character. The system finds solutions in polynomial continuous time, however, at the expense of exponential fluctuations in its energy function.

M. Ercsey-Ravasz, Z. Toroczkai, Nature Physics 7, 966 (2011) doi:10.1038/nphys2105 , arxiv:1208.0526

Echoes in media: Notre Dame News

Research group

Dr. Mária Ercsey-Ravasz

Project director

After obtaining Ph.D. in Physics and Information Technology, Dr. Ercsey-Ravasz have spent 3 years as a postdoctoral researcher at the University of Notre Dame, IN, USA. She returned to Romania to the Babes-Bolyai University with this Starting Research Grant.

homepage, CV , Publications

Dr. Róbert Sumi

Postdoctoral researcher

Dr. Robert Sumi obtained Ph.D. in Physics at the Babes-Bolyai University. He worked 2 years as postdoctoral researcher at the Budapest University of Technology and Economics, Hungary. He joined the research group of Dr. Maria Ercsey-Ravasz at the Babes-Bolyai University in 2012.

CV

Botond Molnár

PhD student

CV