För ett antal slumpmässiga problem med begränsningsnöjdhet, såsom slumpmässig k-SAT och slumpmässig graf/hypergraffärgning, finns det mycket goda uppskattningar av den största begränsningstätheten för vilka lösningar finns. Men alla kända polynom-tidsalgoritmer för dessa problem misslyckas med att hitta lösningar även vid mycket lägre densiteter. För att förstå ursprunget till denna klyfta studerar vi hur strukturen av utrymmet för lösningar utvecklas i sådana problem som begränsningar läggs till. Framför allt bevisar vi att de långt innan lösningarna försvinner organiserar sig i ett exponentiellt antal kluster, som var och en är relativt liten och långt ifrån alla andra kluster. Dessutom är de flesta variabler i varje kluster frysta, dvs. tar bara ett värde. Förekomsten av sådana frysta variabler ger en tillfredsställande intuitiv förklaring till misslyckandet av polynom-tid algoritmer som analyserats hittills. Samtidigt etablerar våra resultat rigoröst en av de två huvudhypoteser som ligger till grund för Survey Propagation, en heurism som har introducerats av fysiker under de senaste åren och som verkar prestera utomordentligt bra på slumpmässiga problem med begränsad tillfredsställelse.
Achlioptas och Ricci-Tersenghi REF var de första att etablera strikt att stelhet uppstår i en slumpmässig begränsning tillfredsställelse problem.
On the solution-space geometry of random constraint satisfaction problems
{'venue': "STOC '06", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}