Tänk dig att du är en tjuv råna ett museum utställning av Kittlande smycken, geoder och sällsynta pärlor. Du är ny på det här, så du tog bara med en enda ryggsäck. Ditt mål bör vara att komma undan med de mest värdefulla föremålen utan att överbelasta din väska tills den bryts eller blir för tung att bära. Hur väljer du bland objekten för att maximera din loot? Du kan lista alla artefakter och deras vikter för att räkna ut svaret för hand., Men ju fler objekt det finns desto mer beskattar denna beräkning blir för en person-eller en dator.
detta fiktiva dilemma, ”ryggsäcksproblemet”, tillhör en klass av matematiska problem som är kända för att driva gränserna för databehandling. Och ryggsäcksproblemet är mer än ett tankeexperiment. ”En hel del problem vi står inför i livet, vare sig det är affärer, finans, inklusive Logistik, containerfartyg lastning, flygplan lastning — det är alla ryggsäck problem”, säger Carsten Murawski, professor vid University of Melbourne i Australien., ”Ur ett praktiskt perspektiv är knapsackproblemet allestädes närvarande i vardagen.”
forskare utnyttjade en gång problemets komplexitet för att skapa datorsäkerhetssystem, men dessa kan nu knäckas eftersom problemet har studerats så väl. Idag, som teknik som kan splittra låsen på vår digitala kommunikation Vävstol vid horisonten, kan knapsack problemet inspirera nya sätt att förbereda sig för den revolutionen.
allt eller inget
knapsackproblemet tillhör en klass av ”NP” – problem, som står för ”nondeterministic polynomial time.,”Namnet refererar till hur dessa problem tvingar en dator att gå igenom många steg för att komma fram till en lösning, och antalet ökar dramatiskt baserat på ingångsstorleken—till exempel inventeringen av föremål att välja mellan när man fyller en viss ryggsäck. Per definition har NP-problem också lösningar som är lätta att verifiera (det skulle vara trivialt att kontrollera att en viss lista över objekt faktiskt passar i en ryggsäck).,
”problemet teoretikerna började titta på var hur effektivt en viss uppgift kan utföras på en dator”, skriver Keith Devlin i boken the Millennium Problems. Till exempel: med tanke på en lista över 1 miljon museiartefakter med sina vikter och monetära värden och en ryggsäck begränsad till 25 pund, skulle en dator behöva springa igenom varje möjlig kombination för att generera den enda med den mest lukrativa drag. Med tanke på en obestämd tid kan en dator använda brute force för att optimera stora fall som detta, men inte på tidsskalor som skulle vara praktiska.,
”Vi tror att du kan täcka hela jorden med processorer och köra dem tills universums värmedöd och fortfarande misslyckas med att lösa relativt små fall av lämpliga versioner av dessa problem”, säger Noah Stephens-Davidowitz, en Microsoft-forskare vid Simons Institute i Berkeley, Kalifornien.
vissa NP-problem som knapsack-exemplet har en speciell egenskap: i början av 1970-talet visade Stephen Cook och Richard Karp att en mängd olika NP-problem kunde omvandlas till ett enda problem med formell logik., Därför, om man kunde lösas och verifieras effektivt med en algoritm, kunde de alla. Den här egenskapen är känd som ” NP fullständighet.”
en av de mest envisa frågorna inom datavetenskap och matematik är om dessa ”NP” – problem, inklusive ryggsäcksproblemet, verkligen skiljer sig från ”P” – problem, de som kan lösas i vad som kallas polynomtid. Om P=NP är det möjligt att lösa alla problem vars lösningar är lätta att verifiera, säger Stephens-Davidowitz. Så, om denna ojämlikhet kvarstår, kommer det allmänna ryggsäcksproblemet alltid att vara svårt.,
hålla saker hemliga
Kryptografiforskare älskar problem som är svåra för datorer att lösa eftersom de är användbara för att kryptera digitala meddelanden. Knapsack-problemliknande säkerhetskoder är inte användbara för detta, eftersom de är för lätt knäckta, men mer komplicerade metoder inspirerade av detta problem utvecklas och kan en dag spela en roll för att överträffa nästa generations databehandling.,
i en tidig knapsack-stil krypteringsmetod skulle en persons privata nyckel vara en lista över nummer där var och en är större än summan av sina föregångare. Utbyten som involverar den personen skulle använda en offentlig nyckel som ser slumpmässigt ut men består av siffror från den första listan med specifika omvandlingar som tillämpas. Till exempel , om den offentliga nyckeln är, skulle det överförda meddelandet ”1, 0, 0, 1” kodas som 2+0+0+5 = 7 (Eftersom 2*1=2, 3*0=0, 4*0=0, och 5 * 1=5). Hemliga nummer som är involverade i konverteringarna mellan tangenterna gör det möjligt att presentera det ursprungliga meddelandet.,
för att detta ska fungera måste en dator också ta reda på om ett visst nummer kan skrivas som summan av en delmängd av siffror i den privata nyckeln, vilket blir ett enkelt ryggsäcksproblem. Det är besläktat med att fylla en ryggsäck med ett parti av sådana olika storlek objekt — som en ring, en målning, en bil och ett hus — och att veta att du inte kan saker i något annat efter att du har kontrollerat att ringen och målningen passar. Kryptografer Ralph Merkle och Martin Hellman beskrev denna idé 1978, men andra räknade ut hur man knäcker den i början av 1980-talet.,
privat informationsutbyte på dagens internet använder ofta nycklar som involverar stora primtal, och medan factoring stora nummer är svårt, är det inte tänkt att tillhöra samma ”NP complete” klass som ryggsäck problemet. Dataforskare är dock redan redo för en framtid där kvantdatorer snabbt kan låsa upp dessa nycklar.
kvantdatorer är beroende av kvantmekanikens principer, som säger att en partikel inte ligger i en enda position men har en sannolikhet att vara på många olika ställen om den inte är fastsatt och uppmätt., Medan normala datorer kodar information i 0s och 1s, skulle varje ”qubit” i en kvantdator ha ett brett spektrum av möjliga tillstånd relaterade till partiklarnas egenskaper. Kvantdatorer skulle inte vara användbara för att surfa på internet eller skriva ett manus i ett kafé, men de skulle släppa lös aldrig tidigare sett ström på några typer av matematiska problem. Tyvärr utgör dessa matematiska problem grunden för modern cybersäkerhet.
”på något sätt fick vi verkligen otur”, säger Stephens-Davidowitz., ”Vi lyckades vila säkerheten på internet på hårdheten hos några av de mycket få problem som verkar vara svårt för klassiska datorer men lätt för kvantdatorer.”
medan quantum computing är i sin linda, säger vissa forskare att vi är bakom i förberedelserna för det. I 2016 krävde National Institute of Standards and Technology (NIST) nya kvantbeständiga krypteringsmetoder och meddelade 26 semifinalister förra året. En sådan typ av algoritm som utvecklas kallas gitterbaserad kryptografi., Istället för att använda siffror använder den nycklar som finns i flera dimensioner och involverar bildandet av en gitterstruktur gjord av lika placerade punkter i rymden. Frågan är var dessa punkter är och hur nära en given slumpmässig punkt är koordinaterna för en gitter. I sitt hjärta är detta ett ryggsäck problem i mer än en dimension.
”min nuvarande besatthet försöker lista ut hur säkra dessa gitterbaserade saker är, helst innan vi använder dem för att köra internet”, säger Stephens-Davidowitz.,
”det betyder att vi behöver kvantbeständig kryptografi mycket tidigare än vi förväntar oss att kvantdatorn når sin fulla potential”, säger Leo Ducas, forskare vid Centrum Wiskunde& Informatica i Nederländerna.
utöver kryptografiforskning är knapsackproblemet och dess NP-kusiner överallt i verkligheten. Till exempel kan du ha hört talas om ”traveling salesman” – problemet, vilket också är NP komplett., Utmaningen här är att hitta den kortaste vägen för en säljare att resa mellan ett visst antal städer innan han återvänder till utgångspunkten. Nära besläktade är fordonets routing problem, som anser att flera fordon gör leveranser.
Luciana Buriol, docent vid Universidade Federal do Rio Grande Do Sul i Brasilien, har attackerat detta problem för att försöka hitta nya metoder för hälso-och sjukvårdssektorn., Hon arbetade med en hemvårdstjänst där läkare och sjuksköterskor besöker patienter i sina hem och hjälpte till att optimera sina vägar, med tanke på ett begränsat antal bilar som är tillgängliga för transport.
”givet 300 patienter och 15 bilar, kan du inte hitta lösningen på en rimlig tid”, sa hon. ”Om du har dagar för att köra algoritmen hittar du – men du måste hitta på mindre än 2 timmar, annars kommer du aldrig att använda i praktiken.”
ingen enskild algoritm som passar alla kan lösa dessa problem., I stället hittar Buriol snabba sätt att komma fram till användbara approximationer så att de kan sättas i handling.
Ryggsäckar runt omkring oss
för dem av oss som inte är Dataforskare och möter dessa typer av problem i det verkliga livet, hur bra är vi? Murawskis grupp finner preliminära resultat att när man ger människor knapsack-liknande problem, kämpar vi också mäktigt., I små experiment där deltagarna ombads att fylla en ryggsäck på en datorskärm med föremål som bär angivna värden och vikter, tenderade människor att ha svårare att optimera ryggsäckens innehåll eftersom antalet objektalternativ ökade—samma problemdatorer har. Forskarna säger att detta konstaterande kan vara relaterat till” choice overload”: hur vi fryser upp när vi får för många val, även i enkla situationer som att köpa sylt i en mataffär.
men i den verkliga världen klarar vi oss. Att uppmärksamma är också ett ryggsäck problem., Vid körning möter vi en cornucopia av möjliga distraktioner som fåglar, moln, radio och omgivande byggnader. Vi måste bara sätta de mest relevanta stimuli i våra mentala ryggsäckar—och i allmänhet gör vi det.
frågan kvarstår: med tanke på att NP fullständiga problem är svårare för datorer än andra typer av conundrums, är de också svårare för människor? De begränsade första resultaten tyder på att de kunde vara, vilket överraskade Murawski.,
”om detta visar sig vara fallet skulle det föreslå att hårdheten hos sådana problem är ett inslag i problemen—en egenskap av naturen—och inte i betraktarens öga”, säger Murawski.