Notre Dame physicists propose solution to constraint satisfaction problems | News | Notre Dame News | University of Notre Dame Skip To Content Skip To Navigation Skip To Search University of Notre Dame Notre Dame News Experts ND in the News Subscribe About Us Home Contact Search Menu Home › News › Notre Dame physicists propose solution to constraint satisfaction problems Notre Dame physicists propose solution to constraint satisfaction problems Published: October 07, 2011 Author: Gene Stowe 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 Nature Physics. 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 microchip design. 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. Contact: Zoltan Toroczkai, 574-631-2618, toro@nd.edu Posted In: Research Home Experts ND in the News Subscribe About Us Related October 05, 2022 Astrophysicists find evidence for the presence of the first stars October 04, 2022 NIH awards $4 million grant to psychologists researching suicide prevention September 29, 2022 Notre Dame, Ukrainian Catholic University launch three new research grants September 27, 2022 Notre Dame, Trinity College Dublin engineers join to advance novel treatment for cystic fibrosis September 22, 2022 Climate-prepared countries are losing ground, latest ND-GAIN index shows For the Media Contact Office of Public Affairs and Communications Notre Dame News 500 Grace Hall Notre Dame, IN 46556 USA Facebook Twitter Instagram YouTube Pinterest © 2022 University of Notre Dame Search Mobile App News Events Visit Accessibility Facebook Twitter Instagram YouTube LinkedIn