At undersøge et uudforsket rum med svære problemer, forskere spiller djævlens advokat

I datalogi, graffarveproblemet er en klassiker. Inspireret af problemet med kortfarvning, den spørger:Givet et netværk af noder forbundet med links, hvad er det mindste antal farver, du skal bruge for at farve hver node, så ingen links forbinder to af samme farve? For et lille antal farver og links, at lede efter en løsning er ligetil:Prøv bare alle mulige kombinationer. Men efterhånden som links øges, problemet bliver mere begrænset – indtil hvis der er for mange links og ikke nok farver, Der findes muligvis ingen løsning overhovedet.

"Så er der disse fascinerende midterzoner, hvor der sandsynligvis er en løsning, men det er meget svært at finde - og en anden, hvor der sandsynligvis ikke er, men det er svært at bevise, at der ikke er, " siger polymat Cris Moore, fastboende professor ved SFI. Det betyder, at konventionelle problemløsningsalgoritmer ikke kan finde dem, han siger. Hvis man starter med en tilfældig farve, for eksempel, og begynder bare at vende farverne på noder, den vil ikke finde en af ​​disse skjulte løsninger.

I et nyt papir præsenteret på 2021-konferencen om læringsteori, Moore og hans samarbejdspartnere beskriver en ny måde at konstruere problemer på med sådanne skjulte løsninger. Gruppen omfatter matematikeren Jess Banks, en tidligere SFI bachelor og post-baccalaureate praktikant, der nu er i gang med en ph.d. ved University of California-Berkeley.

De nærmer sig problemet ved at spille en slags matematisk djævelens advokat. I stedet for at løse problemer, de finder på nyt, komplicerede - med løsninger gemt indeni. "Vi tager den hvide hat af løseren, løsningsfinderen, og vi tager den sorte hat på af den person, der designer vanskelige problemer - næsten som kryptografi, " siger Moore. "Løsningen er skjult."

Forskerne udtænkte en subtil måde at skjule løsninger på, siger Moore. Og når de videregiver disse problemer til problemløsningsalgoritmer, algoritmerne kommer tomme op. "Hvis vi kan skabe problemer, som mange algoritmer ikke kan løse, eller endda fortælle, om der er en løsning, " siger Moore, "så har vi stærke beviser på, at vi har lokaliseret den zone, hvor disse problemer er svære."

Artiklen indeholder en sætning, der beviser, at flere familier af algoritmer ikke formår at finde løsninger på disse genererede problemer. Det betyder, at forskere er tættere end nogensinde på at identificere faseovergangsgrænsen for denne "hårde" zone, hvor det er svært at finde løsninger - eller bevise, at der ikke er nogen.

Moore siger, at den igangværende indsats for præcist at identificere problemer voksede ud af formodninger i fysik, der spørger, hvordan systemer ændrer sig, efterhånden som de bliver mere begrænsede.

"Vores eventyr, " han siger, "har været at gøre disse formodninger og beregninger i fysik til matematiske beviser." Og den eneste måde at blive ved med at skubbe feltet fremad, han siger, er at kalde på de overlappende styrker af værktøjer fra matematik, fysik, og datalogi.