Physicists propose solution to constraint satisfaction problems

Notre Dame physicists propose solution to constraint satisfaction problems

( -- Maria Ercsey-Ravasz, a postdoctoral associate and Zoltan Toroczkai, professor of physics at the University of Notre Dame, have proposed an alternative approach to solving difficult constraint satisfaction problems.

Their paper, "Optimization hardness as transient chaos in an analog approach to constraint satisfaction," was published this week in the journal .

The approach proposed by Ercsey-Ravasz and Toroczkai involves Boolean satisfiability (k-SAT), one of the most studied optimization problems. It applies to a vast range of decision-making, scheduling and operations research problems from drawing delivery routes to the placement of circuitry elements in . The formal proof for the existence or non-existence of fast and efficient (polynomial-time) algorithms to solve such problems constitutes the famous P vs. NP problem. It is one of the six greatest unsolved problems of mathematics, called Millennium Prize Problems, with $1 million allocated to the solution of each problem, awarded by the Clay Institute of Mathematics.

The paper proposes a mapping of k-SAT into a deterministic continuous-time (that is, analog) dynamical system with a unique correspondence between its attractors and the k-SAT solution clusters. It shows that as the constraints are increased, i.e., as the problems become harder, the analog trajectories of the system become transiently chaotic, signaling the appearance of optimization hardness.

The proposed dynamical system always finds solutions if they exist, including for problems considered among the hardest algorithmic benchmarks. It finds these solutions in polynomial continuous-time, however, at the cost of trading search times for unbounded fluctuations in the system’s energy function. The authors establish a fundamental link between optimization hardness and chaotic behavior, suggesting new ways to approach hard optimization problems both theoretically, using nonlinear dynamical systems methods, and practically, via special-purpose built analog devices.

More information: … /full/nphys2105.html

Citation: Physicists propose solution to constraint satisfaction problems (2011, October 10) retrieved 5 December 2023 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

New research reveals brain network connections


Feedback to editors