(PhysOrg.com) -- 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.

**Explore further:**
Professor, former student share prestigious award for problem-solving theory

**More information:**
www.nature.com/nphys/journal/vaop/ncurrent/full/nphys2105.html

## Jarek

I see above article sees the problem with huge amount of constrains such approach is believed to required, like in this paper:

http://citeseerx.....122.726

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 )

## hush1

## hush1

Let's translate this for the salesman and tell him what the above means for him:

When the salesman has so many points to visit - too many points to visit - his movements (trajectories) appear to become chaotic and indeterminate, i.e., random.

The salesman remains undaunted by the description the authors have bestowed upon him. He knows his trajectories are simply misleading the researchers and that his travels are optimal.

The salesman can't wait to meet the researchers and tell them the optimal solution to his problem - regardless of how many points he must visit.

## FMA

## El_Nose

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.

## SemiNerd

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

## hush1

I recommend you follow Grigori Perelman example.

Once you are chosen to accept the prize, turn the prize down.

## Jotaf

Hush1: That would set a nice tradition :)

## SemiNerd

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?

## hush1

http://newsinfo.n...s/22732/

http://docs.googl..._web.pdf Optimization hardness as transient chaos in an analog approach to constraint satisfaction&hl=en&gl=us&pid=bl&srcid=ADGEESjlkfAd-ac7S2ueSunrA4Z7z2wVcOGwypIstyqcrBvkq77zEH8wAfHtHawPxWfrBkHr6xZLfgMYS61HSw2K_As2Tl4aN12GxpMUdtuMHh1MhUCgxSN8WKf5LOu2uRqEURXcsITZ&sig=AHIEtbR3DxM6edghA-oABdr8DxjlD5LGog

He is touching as many bases as possible. Unusual in theoretical physics.

## hush1

I encouraged you. You know exactly how close you are to the optimal in your solutions. Even if the tools - the heuristic means - don't take you to the optimal, you are close.

Never liking an exact solution for optimization?

Don't we both have to laugh at this point? lol

My words were not meant to entice, lure, or trigger a defensive rhetorical question about what you do.

Intuitively, we both know, for the salesman, there exist an exact solution. No can get this close and "Throw their(our) hands in the air and pronounce them (him) unsolvable?"

That rhetorical question answers itself. An answer we both share.