Forestil dig, at du er en tyv, der berøver en museumsudstilling af fristende smykker, geoder og sjældne ædelstene. Du er ny på dette, så du har kun en enkelt rygsæk med. Dit mål skal være at slippe af sted med de mest værdifulde genstande uden at overbelaste din taske, indtil den går i stykker eller bliver for tung til at bære. Hvordan vælger du blandt objekterne for at maksimere din tyvegods? Du kan liste alle artefakter og deres vægte for at udarbejde svaret for hånd., Men jo flere objekter der er, jo mere beskatning bliver denne beregning for en person-eller en computer.
dette fiktive dilemma, “knapsack-problemet”, hører til en klasse af matematiske problemer, der er berømt for at skubbe grænserne for computing. Og rygsækproblemet er mere end et tankeeksperiment. “En masse af de problemer, vi står over for i livet, det være sig erhverv, finans, herunder logistik, container skib lastning, fly ilægning — disse er alle ransel problemer,” siger Carsten Murawski, professor ved University of Melbourne i Australien., “Fra et praktisk perspektiv er rygsækproblemet allestedsnærværende i hverdagen.”
forskere udnyttede engang problemets kompleksitet til at skabe computersikkerhedssystemer, men disse kan nu knækkes, da problemet er blevet så godt undersøgt. I dag, som teknologi, der er i stand til at knuse låsene på vores digitale kommunikationsvæv i horisonten, kan rygsækproblemet inspirere til nye måder at forberede sig på den revolution.
alt eller intet
knapsack-problemet hører til en klasse af “NP” – problemer, der står for “nondeterministisk polynomial tid.,”Navnet referencer, hvordan disse problemer tvinge en computer til at gå gennem mange skridt for at nå frem til en løsning, og antallet stiger dramatisk baseret på størrelsen af input—for eksempel, at opgørelsen af emner at vælge imellem, når fyld en særlig rygsæk. Per definition har NP-problemer også løsninger, der er lette at verificere (det ville være trivielt at kontrollere, at en bestemt liste over varer faktisk passer ind i en rygsæk).,
“problemet teoretikere begyndte at se på, var, hvor effektivt en given opgave kan udføres på en computer,” skriver Keith Devlin i bogen the Millennium Problemer. For eksempel: i betragtning af en liste over 1 millioner museumsgenstande med deres vægte og monetære værdier, og en rygsæk begrænset til 25 pund, skulle en computer gennemgå enhver mulig kombination for at generere den eneste med det mest lukrative træk. I betragtning af en ubestemt tid kunne en computer bruge brute force til at optimere store sager som dette, men ikke på tidsplaner, der ville være praktiske.,
“Vi tror, du kunne dække hele Jorden med processorer og køre dem, indtil varmen død i universet, og stadig ikke er i stand til at løse relativt små forekomster af passende versioner af disse problemer,” siger Noah Stephens-Davidowitz, en Microsoft Research Fellow ved Simons Institute i Berkeley, Californien.nogle NP-problemer som rygsækeksemplet har en særlig egenskab: i de tidlige 1970 ‘ ere viste Stephen Cook og Richard Karp, at en række NP-problemer kunne konverteres til et enkelt problem med formel logik., Derfor, hvis man kunne løses og verificeres effektivt med en algoritme, kunne de alle. Denne egenskab er kendt som ” NP fuldstændighed.”
et af de mest stædige spørgsmål inden for datalogi og matematik er, om disse “NP” – problemer, inklusive rygsækproblemet, virkelig adskiller sig fra “P” – problemer, dem, der kan løses i det, der kaldes polynomial tid. Hvis P=NP, er det muligt at løse ethvert problem, hvis løsninger er lette at verificere, siger Stephens-Davido .it.. Så hvis denne ulighed fortsætter, vil det generelle rygsækproblem altid være svært.,
Holde Ting Hemmelige
Kryptografi forskere love problemer, der er svært for computere at løse, fordi de er nyttige i at kryptere digitale meddelelser. Knapsack-problemlignende sikkerhedskoder er ikke nyttige til dette, da de er for let revnet, men mere komplicerede metoder inspireret af dette problem udvikles og kan en dag spille en rolle i at overvinde den næste generation af computing.,
i en tidlig krypteringsmetode i rygsække-stil ville en persons private nøgle være en liste over tal, hvor hver er større end summen af dens forgængere. Udvekslinger, der involverer denne person, ville bruge en offentlig nøgle, der ser tilfældig ud, men består af tal fra den første liste med specifikke transformationer anvendt. For eksempel , hvis den offentlige nøgle er, vil den transmitterede meddelelse “1, 0, 0, 1” blive kodet som 2+0+0+5 = 7 (Fordi 2*1=2, 3*0=0, 4*0=0, og 5 * 1=5). Hemmelige numre, der er involveret i konverteringerne mellem taster, gør det muligt at afsløre den originale meddelelse.,
for at dette skal fungere, skal en computer også finde ud af, om et givet tal kan skrives som summen af en delmængde af tal i den private nøgle, hvilket bliver et let rygsækproblem. Det er beslægtet med at fylde en rygsæk med et parti af sådanne forskellige størrelser-som en ring — et maleri, en bil og et hus — og at vide, at du ikke kan ting i noget andet, efter at du har kontrolleret, at ringen og maleriet passer. Kryptografer Ralph Merkle og Martin Hellman beskrev denne ID.i 1978, men andre regnede ud, hvordan man knækkede den i begyndelsen af 1980 ‘ erne.,
private informationsudvekslinger på dagens internet bruger ofte nøgler, der involverer store primtal, og selvom det er vanskeligt at factoring store tal, menes det ikke at tilhøre den samme “NP complete” – klasse som knapsack-problemet. Computerforskere er imidlertid allerede klar til en fremtid, hvor kvantecomputere hurtigt kan låse disse nøgler op.
kvantecomputere er afhængige af principperne for kvantemekanik, som siger, at en partikel ikke er placeret i en enkelt position, men har en sandsynlighed for at være mange forskellige steder, medmindre den er fastgjort og målt., Mens normale computere koder for information i 0s og 1s, ville hver “quubit” i en kvantecomputer have en bred vifte af mulige tilstande relateret til partiklernes egenskaber. Kvantecomputere ville ikke være nyttige til at surfe på internettet eller skrive et manuskript i en kaffebar, men de ville frigøre aldrig før set magt på et par typer matematiske problemer. Desværre udgør disse matematiske problemer grundlaget for moderne cybersikkerhed.
“i en vis forstand blev vi virkelig uheldige,” siger Stephens-Davido .it.., “Det lykkedes os at hvile sikkerheden på internettet på hårdheden af nogle af de meget få problemer, der synes at være svært for klassiske computere, men let for kvantecomputere.”
mens kvanteberegning er i sin spædbarn, siger nogle forskere, at vi er bagud med at forberede os på det. I 2016 opfordrede National Institute of Standards and Technology (NIST) til nye kvantebestandige krypteringsmetoder, der annoncerede 26 semifinalister sidste år. En sådan type algoritme, der udvikles, kaldes gitterbaseret kryptografi., I stedet for at bruge tal bruger den nøgler, der findes i flere dimensioner og involverer dannelsen af en gitterstruktur lavet af lige mellemrum i rummet. Spørgsmålet er, hvor disse punkter er, og hvor tæt et givet tilfældigt punkt er til koordinaterne for et gitter. I hjertet er dette et rygsækproblem i mere end en dimension.
” Min nuværende besættelse forsøger at finde ud af, hvor sikre disse gitterbaserede ting er, ideelt før vi bruger dem til at køre internettet,” siger Stephens-Davido .it..,
“Det betyder, at vi har brug for kvante-resistente kryptografi meget tidligere, end vi forventer quantum computer til at nå deres fulde potentiale,” sagde Leo Ducas, forsker ved Centrum Wiskunde & Informatica i Holland.
ud over kryptografiforskning er knapsack-problemet og dets NP-komplette fætre overalt i det virkelige liv. For eksempel har du måske hørt om problemet med “traveling salesman”, som også er NP komplet., Udfordringen her er at finde den korteste rute for en sælger at rejse mellem et givet antal byer, før han vender tilbage til udgangspunktet. Nært beslægtet er køretøjets routing problem, som anser flere køretøjer gør leverancer.
Luciana Buriol, lektor ved Universidade Federal do Rio Grande do Sul i Brasilien, har angrebet dette problem ved at forsøge at finde nye løsninger til sundhedssektoren., Hun arbejdede med en hjemmepleje, hvor læger og sygeplejersker besøger patienter i deres hjem og hjalp med at optimere deres ruter, givet et begrænset antal biler til rådighed til transport.
“i betragtning af 300 patienter og 15 biler kan du ikke finde løsningen inden for en rimelig tid,” sagde hun. “Hvis du har dage til at køre algoritmen, finder du — men du skal finde på mindre end 2 timer, ellers vil du aldrig bruge i praksis.”
ingen enkelt One-si .e-fits-all algoritme kan løse disse problemer., I stedet finder Buriol hurtige måder at nå frem til nyttige tilnærmelser, så de kan sættes i aktion.
rygsække rundt omkring os
For dem af os, der ikke er computerforskere og står over for disse slags problemer i det virkelige liv, hvor gode er vi? Mura .skis gruppe finder foreløbige resultater, at når du giver mennesker rygsæklignende problemer, kæmper vi også mægtigt., I små eksperimenter, hvor deltagerne blev bedt om at udfylde en rygsæk på en computer-skærm med elementer, der transporterer erklærede værdier og vægte, folk tendens til at have en hårdere tid at optimere rygsækken indhold, som er antallet af punkt valg steget—det samme problem computere har. Forskerne siger, at dette fund kan være relateret til” valgoverbelastning”: den måde, vi fryser op, når vi får for mange valg, selv i enkle situationer som at købe marmelade i en købmand.
men i den virkelige verden kommer vi forbi. At være opmærksom er også et rygsækproblem., Når vi kører, står vi over for et overflødighedshorn af mulige distraktioner som fugle, skyer, radioen og de omkringliggende bygninger. Vi må kun lægge de mest relevante stimuli i vores mentale rygsække-og generelt gør vi det.
spørgsmålet er fortsat: i betragtning af at NP komplette problemer er vanskeligere for computere end andre former for conundrums, er de også sværere for folk? De begrænsede indledende resultater antyder, at de kunne være, hvilket overraskede Mura .ski.,
” Hvis dette viser sig at være tilfældet, vil det antyde, at hårdhed af sådanne problemer er et træk ved problemerne—en naturegenskab—og ikke i betragtningens øje,” siger Mura .ski.