Optimization hardness as transient chaos in an analog approach to constraint satisfaction

Maria Ercsey-Ravasz, Zoltan Toroczkai

Boolean satisfiability [1] (k-SAT) is one of the most studied optimization problems, as an efficient (that is, polynomial-time) solution to k-SAT (for $k\ge 3$) implies efficient…