Optimization hardness as transient chaos in an analog approach to constraint satisfaction

Abstract

Boolean satisfiability [1] (k-SAT) is one of the most studied optimization problems, as an efficient (that is, polynomial-time) solution to k-SAT (for $k\ge 3$) implies efficient solutions to a large number of hard optimization problems [2,3]. 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 [4-7], and the boundaries between the basins of attraction [8] of the solution clusters become fractal [7-9], signaling the appearance of optimization hardness [10]. Analytical arguments and simulations indicate that the system always finds solutions for satisfiable formulae even in the frozen regimes of random 3-SAT [11] and of locked occupation problems [12] (considered among the hardest algorithmic benchmarks); a property partly due to the system's hyperbolic [4,13] character. The system finds solutions in polynomial continuous-time, however, at the expense of exponential fluctuations in its energy function.

27 pages, 14 figures

References in corpus (3)

• The multifractal nature of turbulent energy dissipation
• Locked constraint satisfaction problems
• Some remarks on the survey decimation algorithm for K-satisfiability

Cited by in corpus (17)

• A Quantum Model for Coherent Ising Machines: Discrete-time Measurement Feedback Formulation
• Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Slim Fractals: The Geometry of Doubly Transient Chaos
• Realizing interdependent couplings as thermal or higher-order interactions
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• SPICE Modeling of Memcomputing Logic Gates
• A high-performance analog Max-SAT solver and its application to Ramsey numbers
• Solving a directed percolation inverse problem
• Continuous Approximation of the Ising Hamiltonian: Exact Ground States and Applications to Fidelity Assessment in Ising Machines
• Entropic Herding
• Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems
• Are numerical theories irreplaceable? A computational complexity analysis
• On the solvable-unsolvable transition due to noise-induced chaos in digital memcomputing
• Coherence and Transients in Nonlocally Coupled Dissipative Kicked Rotors
• Acceleration of digital memcomputing by jumps
• Econophysics deserves a revamping