Inom datavetenskap, graffärgningsproblemet är en klassiker. Inspirerad av kartfärgningsproblemet, den frågar:Med tanke på ett nätverk av noder sammankopplade med länkar, vad är det minsta antalet färger du behöver för att färga varje nod så att inga länkar kopplar ihop två av samma färg? För ett litet antal färger och länkar, Det är enkelt att leta efter en lösning:Prova bara alla möjliga kombinationer. Men när länkarna ökar, problemet blir mer begränsat - tills om det finns för många länkar och inte tillräckligt med färger, det kanske inte finns någon lösning alls.

"Sedan finns det dessa fascinerande mittzoner där det förmodligen finns en lösning, men det är väldigt svårt att hitta – och ett annat där det förmodligen inte finns, men det är svårt att bevisa att det inte finns, " säger polymaten Cris Moore, en bofast professor vid SFI. Det betyder att konventionella problemlösningsalgoritmer inte kan hitta dem, han säger. Om man börjar med en slumpmässig färg, till exempel, och börjar bara vända färgerna på noderna, det kommer inte att hitta någon av dessa dolda lösningar.

I ett nytt dokument som presenterades vid 2021 års konferens om lärandeteori, Moore och hans medarbetare beskriver ett nytt sätt att konstruera problem med sådana dolda lösningar. I gruppen ingår matematikern Jess Banks, en före detta SFI grund- och post-baccalaureate praktikant som nu bedriver en Ph.D. vid University of California-Berkeley.

De närmar sig problemet genom att spela en slags matematisk djävuls advokat. Istället för att lösa problem, de hittar på nytt, komplicerade sådana — med lösningar gömda inom. "Vi tar av lösarens vita hatt, lösningssökaren, och vi tar på oss den svarta hatten på personen som designar knepiga problem - nästan som kryptografi, " säger Moore. "Lösningen är dold."

Forskarna utarbetade ett subtilt sätt att dölja lösningar, säger Moore. Och när de lämnar över dessa problem till problemlösningsalgoritmer, Algoritmerna kommer upp tomma. "Om vi ​​kan skapa problem som många algoritmer inte kan lösa, eller ens berätta om det finns en lösning, säger Moore, "Då har vi starka bevis för att vi har lokaliserat den zon där dessa problem är svåra."

Uppsatsen innehåller ett teorem som bevisar att flera familjer av algoritmer inte lyckas hitta lösningar på dessa genererade problem. Det betyder att forskare är närmare än någonsin att identifiera fasövergångsgränsen för denna "hårda" zon där det är svårt att hitta lösningar - eller bevisa att det inte finns några.

Moore säger att den pågående ansträngningen att exakt identifiera problem växte fram ur gissningar inom fysiken som frågar hur system förändras när de blir mer begränsade.

"Vårt äventyr, " han säger, "har varit att förvandla dessa gissningar och beräkningar i fysik till matematiska bevis." Och det enda sättet att fortsätta driva fältet framåt, han säger, är att åberopa de överlappande styrkorna hos verktyg från matematik, fysik, och datavetenskap.