Matematikkgåte fra flere tiår siden endelig løst etter å ha blitt tapt og funnet av forskere

En representasjon av de tre verktøyene problemet, med linjer krysset. (Koko90/Wikimedia Commons/CCB-SA 3.0)

Et par danske dataforskere har løst et mangeårig matematikkoppgave som lå i dvale i flere tiår, etter at forskere ikke klarte å gjøre betydelige fremskritt med det siden 1990-tallet.

Det abstrakte problemet det er snakk om er en del av det som kalles grafteori , og gjelder spesifikt utfordringen med å finne en algoritme for å løse planheten til en dynamisk graf. Det høres kanskje litt skremmende ut, så hvis grafteorien din er litt rusten, er det en mye morsommere og mer tilgjengelig måte å tenke på de samme iboende ideene.

Går vi så langt tilbake som 1913 – selv om de matematiske begrepene sannsynligvis kan spores mye lenger tilbake – et puslespill kalt problem med tre verktøy ble publisert.



Enkelt sagt, forestill deg at det er tre hus på rekke og rad, som du kan tegne på et stykke papir. Under dem kan du også tegne tre separate verktøy: vann, gass og elektrisitet.

Tre verktøysløsning med én linjekryss. ( CMG Lee/Wikimedia Commons/CC BY-SA )

Utfordringen er å tegne linjer på denne enkle grafen, som kobler de tre verktøyene til hvert hus. Men det er et problem: ingen av linjene (totalt ni) på papiret har lov til å krysse hverandre. Kan du tenke deg en måte å slå sammen alt uten at noen av forbindelsene krysser hverandre?

I den mest konvensjonelle forstand – på et vanlig, todimensjonalt papirark, som et eksempel på en plan graf – det er ikke mulig å løse problemet med tre verktøy. Selv om det er ubeleilig, kan ikke alle disse husene motta tilkoblingene sine.

Men problemet med tre verktøy er ikke et puslespill så mye som skal løses, men snarere et eksempel på hvordan noen typer grafnettverk ikke er plane - det vil si i stand til å ha kanter (linjer) som forbinder de forskjellige hjørnene deres (hus og verktøy) uten at linjene krysses.

Når du har å gjøre med mer komplekse grafer som involverer flere hjørner, Kuratowskis teorem hjelper matematikere med å finne ut om grafer er plane eller ikke, og siden 1970-tallet har forskere også utviklet algoritmer for å gjøre det samme raskere.

Likevel etter en finale algoritmisk fremskritt på 1990-tallet , ble det ikke gjort noen vesentlige fremskritt på dette området på flere tiår, i hvert fall ikke med hensyn til algoritmer som kan løse for dynamiske (endrende) grafer.

Spol frem til fjoråret, og informatikere Jacob Holm fra Københavns Universitet og Eva Rotenberg fra Danmarks Tekniske Universitet var i gang med problemet.

'Vi hadde nesten gitt opp å få den siste brikken og løse gåten,' sier Holm . 'Vi tippet at det i beste fall ville være fem års arbeid til før vi ville være i stand til å løse gåten.'

Det var på det tidspunktet, nesten ved en tilfeldighet, de innså at de effektivt allerede hadde løst mesteparten av problemet i et annet stykke forskning – en forhåndsutskrift om relaterte plankonsepter, som paret ble utgitt online i 2019 .

Med den skjulte løsningen som allerede var publisert, skravlet paret i løpet av de påfølgende ukene, og skrev et formelt bevis på deres forbedring av grafalgoritmen, som ikke hadde sett forbedring siden 1990-tallet.

«Vi jobbet med artikkelen uten stans, i fem til seks uker. Og den endte opp med å fylle mer enn 80 sider,' sier Rotenberg .

Resultatene, nå publisert , gir en algoritme som tar minst beregningstid ennå for å løse spørsmålet om en dynamisk graf – med forbehold om innsettinger og slettinger av kanter som forbinder dens toppunkter – kan støtte en plan innbygging. (Forenklet sagt, om det kan tegnes på et stykke papir uten at linjer blir krysset.)

Det er et stort fremskritt, siden de samme vanskelighetene som finnes i noe så konseptuelt enkelt som problemet med de tre verktøyene, blir mye mer ufattelige i felt som mikrobrikkedesign eller veiplanlegging, der det er mye flere hjørner involvert enn bare tre hus og tre verktøy.

'Det viser seg at for dynamiske grafproblemer er det ofte mulig å bygge en eller annen datastruktur som kan brukes til å beregne svaret på nytt etter hver endring av grafen mye raskere enn å beregne svaret på nytt fra bunnen av,' Holmes forklarer .

'Dette resultatet er selvfølgelig en enorm personlig seier for oss.'

Funnene er rapportert i STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing .

Populære Kategorier: Rom , Samfunn , Ukategorisert , Mennesker , Natur , Fysikk , Miljø , Mening , Forklarer , Helse ,

Om Oss

Publisering Av Uavhengige, Beviste Fakta Om Rapporter Om Helse, Rom, Natur, Teknologi Og Miljø.