Physicists propose solution to constraint satisfaction problems

October 10, 2011, University of Notre Dame

( -- 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.

Explore further: New research reveals brain network connections

More information: … /full/nphys2105.html

Related Stories

New research reveals brain network connections

July 13, 2011

Research conducted by Maria Ercsey-Ravasz and Zoltan Toroczkai of the University of Notre Dame's Interdisciplinary Center for Network Science and Applications (iCeNSA), along with the Department of Physics and a group of ...

Optimization server reaches two million milestone

February 17, 2010

NEOS, the Network-Enabled Optimization System developed by researchers at the U.S. DOE's Argonne National Laboratory in conjunction with Northwestern University, has reached a new milestone: two million submissions to its ...

After almost 20 years, math problem falls

July 18, 2011

Mathematicians and engineers are often concerned with finding the minimum value of a particular mathematical function. That minimum could represent the optimal trade-off between competing criteria — between the surface ...

Recommended for you

Coffee-based colloids for direct solar absorption

March 22, 2019

Solar energy is one of the most promising resources to help reduce fossil fuel consumption and mitigate greenhouse gas emissions to power a sustainable future. Devices presently in use to convert solar energy into thermal ...

Physicists reveal why matter dominates universe

March 21, 2019

Physicists in the College of Arts and Sciences at Syracuse University have confirmed that matter and antimatter decay differently for elementary particles containing charmed quarks.

ATLAS experiment observes light scattering off light

March 20, 2019

Light-by-light scattering is a very rare phenomenon in which two photons interact, producing another pair of photons. This process was among the earliest predictions of quantum electrodynamics (QED), the quantum theory of ...

How heavy elements come about in the universe

March 19, 2019

Heavy elements are produced during stellar explosion or on the surfaces of neutron stars through the capture of hydrogen nuclei (protons). This occurs at extremely high temperatures, but at relatively low energies. An international ...


Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (1) Oct 10, 2011
Most of the fight with the P=NP question was made through unsuccessful discrete approach. Translating it into continuous problem moves it to completely different kingdom of analysis, which is practically unexplored.
I see above article sees the problem with huge amount of constrains such approach is believed to required, like in this paper:
But it occurred that constrains are not required: k-SAT can be translated into just optimization of nonnegative polynomial, for example (x OR y) can be changed into optimizing
((x-1)^2 plus y^2)((x-1)^2 plus (y-1)^2)(x^2 plus (y-1)^2)
and correspondingly 14 degree polynomial for alternatives of 3 variables. Zeros of sum of such polynomials for 3-SAT terms corresponds to the solution. Its gradient flow is dynamical system like it the article, but without constrains.
( http://www.usenet...&p=0 )
1 / 5 (1) Oct 10, 2011
Kind of fuzzy logic?
not rated yet Oct 10, 2011
fuzzy logic is where you take a classic problem with two solutions say is the light on -- yes / no - or 1/0 -- and the fuzzy equivalent is kind of like making logic understand terms like mostly, kind of, and slightly. so is the light on is no longer yes - it is slightly on - no longer 1 for yes but .25

Fuzzy logic allows a computer to evaluate the question - is the car going fast -- well the discrete measure of speed is 55mph and that equates to say .60 for fast but a discrete measure of 95 mph would translate into .95. The equation that translates a discrete measure to its fuzzy answer does not need to be a linear equation - but it must satisfy the condidtion of an answer between 0 - 1.
not rated yet Oct 10, 2011
The overall effectiveness of this algorithm will in the end be determined by how long it takes to compute the solutions to practical problems. After all, Quick-Sort is O(n*n) while Merge- Sort is O(n*logn), but for most problems (even very large ones) qsort with a random pivot is faster.

I solve the kinds of problems this new algorithm addresses in my every day work. I look forward to seeing what (if any) results are published on practical chip design layout optimization (for example).
not rated yet Oct 10, 2011
Can anyone access the article and share the PDF please? My department doesn't subscribe to Nature Physics.

Hush1: That would set a nice tradition :)
not rated yet Oct 10, 2011
Then solve exactly the traveling salesman problem. And line your pocketbook with $1 million allocated to the solution.

I recommend you follow Grigori Perelman example.
Once you are chosen to accept the prize, turn the prize down.

I never said that we solve the problems optimally. There are a large number of companies out there that solve these and other NP-complete type problems using heuristics. We can never be as optimal as we like of course.

Every printed circuit board, chip layout, and other design solution requires (as close as possible) solutions to these problems. What do you think we do? Throw our hands in the air and pronounce them unsolvable?

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.