[Hard optimization problems paper] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Hard optimization problems paper

(Click here to view the original thread with full colors/images)


Posted by: Jason Cawley

There was an interesting paper on combinatorial optimization problems in the most recent, June 9 issue of Nature. I consider it reasonably related to NKS, especially to the systems based on constraints material at the end of chapter 5 (see 210 and following pages, e.g.)

Rigorous location of phase transitions in hard optimization problems

Dimitris Achlioptas, Assaf Naor and Yuval Peres

It is widely believed that for many optimization problems, no algorithm is substantially more efficient than exhaustive search. This means that finding optimal solutions for many practical problems is completely beyond any current or projected computational capacity. To understand the origin of this extreme 'hardness', computer scientists, mathematicians and physicists have been investigating for two decades a connection between computational complexity and phase transitions in random instances of constraint satisfaction problems. Here we present a mathematically rigorous method for locating such phase transitions. Our method works by analysing the distribution of distances between pairs of solutions as constraints are added. By identifying critical behaviour in the evolution of this distribution, we can pinpoint the threshold location for a number of problems, including the two most-studied ones: random k-SAT and random graph colouring. Our results prove that the heuristic predictions of statistical physics in this context are essentially correct. Moreover, we establish that random instances of constraint satisfaction problems have solutions well beyond the reach of any analysed algorithm.

For those with Nature subscriptions, you can find the whole article here -

http://www.nature.com/nature/journa...ature03602.html




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings