Hversu margir hnútar eru til? Nýtt tölvubragð er að leysa svarið

ÞAÐ var á sínum tíma einn sá pirrandi hluti allra ferða með almenningssamgöngum. Þú kreistir þig fram hjá hinum líkunum, sest niður og fiskar heyrnartólin upp úr vasanum. Þú nenntir ekki að vinda vírunum upp í snyrtilega lykkju síðast þegar þú notaðir þá og því – andvarp – þarftu nú að eyða næstu 5 mínútunum í að leysa þennan hnút. Guði sé lof fyrir uppfinningu þráðlausra heyrnartóla.

Hnútar eru þó ekki bara hversdagslegur pirringur. Þeir eru líka uppspretta endalauss innblásturs fyrir vísindamenn. Tökum stærðfræðinginn Benjamin Burton , sem er heillaður af einni einfaldri spurningu: hversu margir hnútar eru til? „Það er eitthvað pirrandi við vandamál sem hægt er að lýsa fyrir 10 ára barni, en sem stærðfræðingar hafa ekki enn leyst,“ segir hann.

Að taka hnútatalning er eitt af þessum vandamálum sem ætti að vera ómögulegt að leysa vegna þess hve flókið það er. Það eru svo margar leiðir sem hægt er að krossa og hringja yfir strengina að jafnvel hraðskreiðasta tölvan gæti aldrei skráð þá alla. Samt hefur Burton verið að gefa kost á sér og í leiðinni sýnir hann að með nokkrum snjöllum reiknibrögðum, stærðfræðivandamál sem virðast óyfirstíganleg eru kannski ekki.

Hnútar og vísindi hafa verið, ahem, flækt í töluverðan tíma. Á deyjandi áratugum 19. aldar voru vísindamenn að glíma við hvernig ætti að skilja atóm. Ein tilgátan leit á þá sem litla hvirfla af vökva sem urðu stöðugar þegar þær voru hnýttar. Kelvin lávarður, sem varð forseti Konunglega félagsins í Bretlandi, var fyrstur til að leggja til að hver efnaþáttur samsvaraði annarri tegund af hnút.

Hugmyndin var yfirgefin eftir uppgötvun rafeindarinnar, en á þeim tíma virtist mikilvægt að skilja hnúta. Eðlisfræðingurinn Peter Guthrie Tait var fyrstur til að gera hníf við að búa til yfirgripsmikinn lista yfir þá. Spil á borðinu: það eru óendanlega margir mögulegir hnútar, því þú getur haldið áfram að bæta við auka hnútum að eilífu. Spurningin sem stærðfræðingar hafa áhuga á er lúmskari. Einkenni hnúts er krossnúmer hans, fjöldi skipta sem strengirnir krossast. Spurningin er, fyrir tiltekinn fjölda yfirferða, hversu margir mismunandi hnútar eru mögulegir? Árið 1885 íhugaði Tait, í samstarfi við stærðfræðinginn Thomas Kirkman, alla hnúta með allt að og með 10 þverum. Hann teiknaði þær allar í höndunum og setti saman 364 stillingar í töflu.

Reyndu að ganga lengra og hlutirnir verða fljótt miklu erfiðari. Eftir því sem þú leyfir fleiri yfirferðir, fjölgar mögulegum hnútum hratt. Síðasta stóra framlengingin á hnútatöflunum var gefin út árið 1998. Stærðfræðingarnir Jim Hoste, Morwen Thistlethwaite og Jeff Weeks skráðu alla hnútana upp að og með 16 þverum – allar 1,7 milljónir þeirra .

Að fara út fyrir þetta hefur, þar til nýlega, verið óframkvæmanlegt. Til að sjá hvers vegna þurfum við að vita aðeins meira um hvernig stærðfræðingar hugsa um hnúta (sjá „ Hvenær er hnútur ekki hnútur? “). Ólíkt raunverulegum hnútum sem oft eru strengjastykki með lausum endum, eru stærðfræðilegir hnútar lokaðir. Ímyndaðu þér að binda hnút í spaghettístykki og blanda síðan lausu endum saman.

Teygja, snúa, beygja

Stærðfræðingar meðhöndla hnúta eftir reglum staðfræðinnar, grein rúmfræðinnar. Þetta segir að hnútur haldist í grundvallaratriðum sá sami ef þú teygir, snýrð eða beygir þræðina – en að gera klippingar eða nýjar samskeyti er nei-nei. Þetta leiðir til hugmyndarinnar um aðalhnút, hnút sem er ekki hægt að skipta stærðfræðilega niður í tvo eða fleiri einfaldari hnúta.

Starfið við að setja saman hnúta snýst því um að bera saman vandaða flækjur til að sjá hvort þeir séu í raun sami aðalhnúturinn. Ekki vanmeta hversu erfitt þetta getur verið. Í 75 ár voru tveir hnútar með 10 þverum skráðir sérstaklega í töflum. En árið 1973 áttaði Kenneth Perko, lögfræðingur í New York sem hafði lært stærðfræði, að ef þú tekur spegilmynd af einum geturðu hagrætt henni til að verða jafngildur hinu. Hnútarnir eru þekktir sem „Perko parið“.

Þegar tekist er á við milljónir hnúta verður starfið við að bera kennsl á tvígangara svo tímafrekt að jafnvel hröðustu ofurtölvur ættu ekki að vera fræðilega færar um það á hæfilegum tíma. Samt sem áður, árið 2019, ákvað Burton, sem hefur aðsetur við háskólann í Queensland í Ástralíu, að tíminn væri kominn til að taka þátt.

Hann vissi að það er munur á hnútaflokkunaralgrími í ágripi og hvernig það reiknirit er útfært í tölvukóða. Listin að brúa þetta bil er þekkt sem reiknirit verkfræði og Burton hélt að með réttum brellum væri vandamálið ekki eins erfitt og það virtist. „Hluti af því sem hvatti mig var að búa til sýningargrip til að sjá hvort tækin væru nógu góð,“ segir hann.

Hann byrjaði á því að setja tölvu í það verkefni að láta sig dreyma um allar mögulegar leiðir til að hnýta strengi með allt að 19 krossum. Þetta er tiltölulega einfalt verkefni og tölvan spýtti út 21 milljarði hnúta umsækjenda eftir örfáa daga.

Starfið var síðan að athuga að hver hnútur væri fínn og áberandi. Þetta felur í sér að geyma fulla staðfræðilega lýsingu á hnútunum í vinnsluminni tölvu eða vinnsluminni. Gagnasett upp á 21 milljarð hnúta myndi þurfa meira en 1 terabæt af vinnsluminni til að geyma og tölvur með það magn eru sjaldgæfar. Til að komast í kringum þetta notaði Burton hugbúnaðarpakka sem hann hefur þróað sem heitir Regina. Það getur umbreytt hnútum í „hnútaundirskriftir“, strengi af bókstöfum sem fanga helstu staðfræðilega eiginleika hvers flækju. Hægt er að geyma undirskriftirnar mun hagkvæmara en hnútalýsingu. Auk þess hafa hnútar sem flækjast á annan hátt en eru í raun jafngildir með sömu undirskrift, sem gerir það auðvelt að eyða afritum. Burton tókst að minnka frambjóðendahnútana í um 7 milljarða á dag.

Þessi aðferð var hins vegar ekki nógu öflug til að bera kennsl á hvert síðasta afrit. Næsta aðferð Burtons fól í sér að reikna út það sem er þekkt sem óbreytileiki hnúta fyrir hvern frambjóðandahnút. Óbreytileikar eru stærðfræðilegir hlutir sem fanga kjarna hnúts – ef tveir hnútar hafa mismunandi óbreytileika eru þeir ólíkir hnútar. Óbreytanlegir þættir eru öflugri en undirskriftir, en erfiðara er að reikna þær út: það hefði tekið tölvu Burtons meira en ár að reikna þær út fyrir alla þá hnúta sem eftir eru. Með því að flokka þær í hópa og keyra þær á samhliða ofurtölvum komst hann í gegnum þær á dögum. Laugin var komin niður í 370 milljónir.

Burton þurfti einnig að glíma við hnúta sem ekki voru ofsóttir, sérstaklega krefjandi flokkur. En eftir fleiri umferðir af flokkun varð hið meinta ómögulega mögulegt. Manntal Burtons stækkaði hnútatöflurnar til að ná yfir allt að og með 19 yfirferðum. Lokatölur: 352.152.252 hnútar.

Ian Agol við háskólann í Kaliforníu í Berkeley segist vera hrifinn af útreikningunum. „Það mun líklega vera gagnlegt fyrir stærðfræðinga sem leita að hnútum með sérstaka eiginleika, eða sem hafa hnút sem þeir vilja þekkja,“ segir hann.

Hann og aðrir stærðfræðingar telja að verk Burtons sé einnig glæsilegt dæmi um reiknirit verkfræði. „Þetta er vaxandi stefna í hreinni stærðfræði, þar sem reikniaðferðir eru notaðar á skapandi hátt,“ segir Hans Boden við McMaster háskólann í Ontario, Kanada.

Vörubílar og myndavélar

Það eru fullt af hagnýtum vandamálum þar sem reikniritverkfræði er notuð til að finna skilvirkar lausnir á erfiðum vandamálum. Sumir af mikilvægustu eru í flutningum, þar sem Bjartsýni leið getur sparað tíma og miklar fjárhæðir. Aðrir eru meðal annars að vinna út hvernig eigi að hylja rými með CCTV myndavélum. Í mörgum tilfellum er ómögulegt að fá fullkomna lausn á hæfilegum tíma.

Þetta er líka raunin þegar kemur að því að kortleggja flókna þróunarsögu, sérstaklega fyrir plöntur og bakteríur. Reiknirit eru notuð til að tengja saman DNA gögn í fylgnitrjám, línurit sem flokka náskyldar tegundir nánar en fjarskyldar. Hins vegar berast gen stundum ekki frá foreldri til afkvæma, heldur í gegnum það sem er þekkt sem lárétt genaflutning frá einni tegund til annarrar. Reiknirit sem eru hönnuð til að kortleggja þessar millifærslur geta verið mjög hægar.

Eitt reikniritverkfræðihakk til að komast í kringum þetta felur í sér að stilla gagnainntak til að gera þau minni. Til dæmis, ef þú lagar fjölda hugsanlegra stökkbreytinga sem þú ert að íhuga, er hægt að leysa vandamálið á skilvirkan hátt. Nýlega beittu Edwin Jacox, nú við háskólann í Kaliforníu í Santa Cruz, og samstarfsmenn hans þessa aðferð á sýanóbakteríur sýlógenísk tré. Sýanóbakteríur léku stórt hlutverk í breyttu lífríki jarðar fyrir meira en 2 milljörðum ára. Vísindamennirnir þróuðu reiknirit með breytilegum hætti sem endurbyggir sýanóbakteríurnar á aðeins 15 sekúndum .

Hvort sem það er að endurbyggja þróunartré eða skrá hnúta, þá er ljóst að hægt er að gera erfiðustu tölvuvandamálin meðfærileg. „Með reiknirit verkfræði og heuristics reynast hlutir sem eru hægir í reynd vera ótrúlega, furðu fljótir,“ segir Burton. Það þýðir að jafnvel erfiðustu vandamálin þurfa ekki að skilja okkur eftir í óumflýjanlegum flækjum.

Hvenær er hnútur ekki hnútur?

Hér er vandamál sem þarf að taka úr: ef þú togar í sóðalegan víraflækju, hvernig veistu hvort það flækist bara meira eða losnar í einfalda lykkju? Þetta er vandamál sem stærðfræðingar kalla „unknot recognition“ og það er vandamál sem við gætum brátt leyst. Óhnútaþekking heillar jafnt stærðfræðinga og tölvunarfræðinga vegna þess að hún er hluti af hinni frægu „P vs NP“ spurningu.

Til að sjá hvernig það virkar skaltu taka hið klassíska ferðasöluvandamál, þar sem við verðum að finna stystu leiðina fyrir sölumann til að heimsækja nokkrar borgir. Ef reiknirit sem er hannað til að leysa þetta vandamál verður ekki veldishraða eftir því sem fleiri borgir eru teknar með, er sagt að það sé „P“. Þetta þýðir að það er leysanlegt í hæfilegum – eða margliðu, í stærðfræði tala – tíma. Þegar þú hefur svarið þarftu að athuga að það sé rétt. Ef auðvelt er að athuga svarið þitt er vandamálið flokkað sem „NP“. Stóra spurningin fyrir stærðfræðinga er hvort öll NP-dæmi séu líka P. Þetta er eitt af Þúsaldarverðlaunadæmunum – svaraðu því með óyggjandi hætti og þú munt vinna milljón.

Óhnútaþekking býr í rökkrinu svæði P vs NP. Við vitum nú þegar að þetta vandamál er örugglega „NP“ eða auðvelt að athuga það. Ef reikniritið þitt getur framleitt óhnúta lykkju geturðu strax séð að það hefur virkað. Stærðfræðingar telja líka líklegt að það sé P, og við erum pirrandi nálægt því að sanna það.

Árið 2014 þróaði Benjamin Burton við háskólann í Queensland í Ástralíu óhnýtt reiknirit sem í reynd leysist á margliða tíma. Reiknirit hans hefur staðist „fyrir hvern hnút sem við höfum kastað á það hingað til,“ segir hann. Nýlega, Marc Lackenby við háskólann í Oxford þróað óhnúta auðkenningaralgrím sem er „quasi-P“ (sem þýðir á stærðfræðimáli „næstum því“). Ólíklegt er að honum verði breytt í keyranlegan tölvukóða vegna þess að hann er svo flókinn, en Lackenby er viss um að einfölduð útgáfa „verði virkilega hagnýt“.

Að sýna að óhnúta viðurkenning er bæði P og NP mun ekki leysa víðtækari Þúsaldarverðlaunavandann, þó það gæti gefið okkur gagnlegar ábendingar. Samt er þetta mikilvægur áfangi og stærðfræðingar munu fagna þegar við komum þangað.