1.2 SATISFIABILITY AND HARD-PROBLEM INSTANCES....... iv
“NP-complete”problemsareat thecoreof many computational tasksof practical interest,whichmeansthatthecostof solutionwill grow exponentiallywith problem sizein the worst case(providedP  NP). Althoughheuristicscanbe quite effective on suchproblemsin most cases,thereis a growing appreciationthat theseproblemscontainphasetransitions,andat thephaseboundariesexponential complexity becomesthetypical outcome,not just theworstcase.Usingmethods from statisticalphysics,a much betterunderstandingof suchphasetransition phenomenain computationalproblemshasbeenobtainedin recentyears. We will review severalkey resultsin this area,therebyillustratingsomeof thedeep connectionsbetweencomputerscienceandstatisticalphysics.Theseminalwork by Fu andAnderson[13, 14] providedtheinitial impetusfor muchof this work.