stel je voor dat je een dief bent die een museumtentoonstelling berooft van verleidelijke Sieraden, geodes en zeldzame edelstenen. Je bent hier nieuw in, dus je hebt maar één rugzak meegenomen. Uw doel moet zijn om weg te komen met de meest waardevolle objecten zonder overbelasting van uw tas totdat het breekt of wordt te zwaar om te dragen. Hoe kies je uit de objecten om je buit te maximaliseren? Je kunt alle artefacten en hun gewichten opsommen om het antwoord met de hand uit te werken., Maar hoe meer objecten er zijn, hoe zwaarder deze berekening wordt voor een persoon—of een computer.
dit fictieve dilemma, het” knapzak probleem”, behoort tot een klasse van wiskundige problemen die bekend staan om het verleggen van de grenzen van computing. En het ranselprobleem is meer dan een gedachte-experiment. “Veel problemen waarmee we in het leven worden geconfronteerd, of het nu zakelijk, financieel, inclusief logistiek, containerschepen Laden, vliegtuigen Laden — dit zijn allemaal knapzakproblemen,” zegt Carsten Murawski, professor aan de Universiteit van Melbourne in Australië., “Vanuit een praktisch perspectief is het rugzakprobleem alomtegenwoordig in het dagelijks leven.”
onderzoekers maakten ooit gebruik van de complexiteit van het probleem om computerbeveiligingssystemen te creëren, maar deze kunnen nu worden gekraakt omdat het probleem zo goed is bestudeerd. Nu technologie die de sloten van onze digitale communicatie kan verbrijzelen aan de horizon opdoemt, kan het rugzakprobleem nieuwe manieren inspireren om zich voor te bereiden op die revolutie.
alles of niets
het knapzak-probleem behoort tot een klasse van “NP” – problemen, wat staat voor “niet-deterministische polynoomtijd”.,”De naam verwijst naar hoe deze problemen een computer dwingen om door vele stappen te gaan om tot een oplossing te komen, en het aantal neemt dramatisch toe op basis van de grootte van de ingangen—bijvoorbeeld, de inventaris van items om uit te kiezen bij het vullen van een bepaalde ransel. Per definitie hebben NP-problemen ook oplossingen die gemakkelijk te controleren zijn (het zou triviaal zijn om te controleren of een bepaalde lijst van items in feite in een rugzak past).,”The problem the theoretici started to look at was how efficient a particular task can be carried out on a computer”, schrijft Keith Devlin in het boek The Millennium Problems. Bijvoorbeeld: gegeven een lijst van 1 miljoen museum artefacten met hun gewichten en monetaire waarden, en een rugzak beperkt tot 25 pond, een computer zou moeten lopen door elke mogelijke combinatie om de ene met de meest lucratieve trek te genereren. Gegeven een onbepaalde tijd, kan een computer brute kracht gebruiken om grote gevallen als deze te optimaliseren, maar niet op tijdschalen die praktisch zou zijn., “We denken dat je de hele aarde met processors kunt bedekken en ze kunt laten draaien tot de hitte van het universum sterft en nog steeds niet in staat bent om relatief kleine gevallen van geschikte versies van deze problemen op te lossen,” zegt Noah Stephens-Davidowitz, een Microsoft Research Fellow aan het Simons Institute in Berkeley, Californië.
sommige NP-problemen zoals het knapzak-voorbeeld hebben een speciale eigenschap: begin jaren zeventig toonden Stephen Cook en Richard Karp aan dat verschillende NP-problemen konden worden omgezet in één enkel probleem van de formele logica., Daarom, als men efficiënt kon worden opgelost en geverifieerd met een algoritme, konden ze allemaal. Deze eigenschap staat bekend als ” NP volledigheid.”
een van de meest hardnekkige vragen in de informatica en wiskunde is of deze “NP” – problemen, inclusief het ranselprobleem, echt verschillen van “P” – problemen, die kunnen worden opgelost in de zogenaamde polynoomtijd. Als P = NP, dan is het mogelijk om elk probleem op te lossen waarvan de oplossingen gemakkelijk te verifiëren zijn, zegt Stephens-Davidowitz. Dus, als deze ongelijkheid blijft bestaan, zal het algemene ransel probleem altijd moeilijk zijn.,
dingen geheim houden
cryptografie onderzoekers houden van problemen die moeilijk op te lossen zijn voor computers omdat ze nuttig zijn bij het versleutelen van digitale berichten. Knapsack-probleem – achtige beveiligingscodes zijn niet nuttig voor dit, omdat ze te gemakkelijk gekraakt, maar meer ingewikkelde methoden geïnspireerd door dit probleem worden ontwikkeld, en kunnen op een dag een rol spelen in het te slim af zijn van de volgende generatie van computing.,
in een vroege versleutelingsmethode in knapzak-stijl zou de persoonlijke sleutel van een persoon een lijst van getallen zijn waarvan elk groter is dan de som van zijn voorgangers. Uitwisselingen waarbij die persoon betrokken is, zouden een publieke sleutel gebruiken die er willekeurig uitziet, maar bestaat uit getallen uit de eerste lijst met specifieke transformaties die worden toegepast. Bijvoorbeeld, als de publieke sleutel is, het verzonden bericht “1, 0, 0, 1” zou worden gecodeerd als 2+0+0+5 = 7 (omdat 2*1=2, 3*0=0, 4*0=0, en 5 * 1=5). Geheime nummers die betrokken zijn bij de conversies tussen sleutels maken het mogelijk om het originele bericht te onthullen.,
om dit te laten werken, moet een computer ook uitzoeken of een gegeven getal kan worden geschreven als de som van een subset van getallen in de private sleutel, wat een eenvoudig knapzak probleem wordt. Het is verwant aan het vullen van een rugzak met een partij van dergelijke verschillend formaat items — zoals een ring, een schilderij, een auto en een huis — en wetende dat je niet kunt spullen in iets anders nadat je hebt gecontroleerd of de ring en het schilderij passen. Cryptografen Ralph Merkle en Martin Hellman beschreven dit idee in 1978, maar anderen ontdekten hoe het te kraken door de vroege jaren 1980.,
privé-informatie-uitwisselingen op het huidige internet maken vaak gebruik van sleutels waarbij grote priemgetallen betrokken zijn, en hoewel het moeilijk is om grote getallen in rekening te brengen, wordt aangenomen dat het niet tot dezelfde klasse “NP complete” behoort als het knapzakprobleem. Computerwetenschappers maken zich echter al op voor een toekomst waarin quantumcomputers deze sleutels snel kunnen ontgrendelen.
kwantumcomputers vertrouwen op de principes van de kwantummechanica, die zegt dat een deeltje zich niet op een enkele positie bevindt, maar een kans heeft om zich op veel verschillende plaatsen te bevinden, tenzij het wordt vastgezet en gemeten., Terwijl normale computers informatie coderen in 0s en 1s, zou elke” qubit ” in een kwantumcomputer een breed scala van mogelijke toestanden hebben met betrekking tot de eigenschappen van deeltjes. Quantumcomputers zouden niet handig zijn voor het surfen op het internet of het schrijven van een scenario in een coffeeshop, maar ze zouden nooit eerder gezien macht ontketenen op een paar soorten wiskundige problemen. Helaas vormen die wiskundeproblemen de basis van moderne cybersecurity.
” In zekere zin hebben we echt pech, ” zegt Stephens-Davidowitz., “We zijn erin geslaagd om de veiligheid van het internet te laten rusten op de hardheid van enkele van de weinige problemen die moeilijk lijken te zijn voor klassieke computers, maar gemakkelijk voor kwantumcomputers.”
terwijl quantum computing in de kinderschoenen staat, zeggen sommige onderzoekers dat we achterlopen in de voorbereiding. In 2016 riep het National Institute of Standards and Technology (NIST) op tot nieuwe kwantumbestendige encryptie-methoden en kondigde vorig jaar 26 halve finalisten aan. Een dergelijk type algoritme wordt ontwikkeld heet rooster-gebaseerde cryptografie., In plaats van getallen te gebruiken, gebruikt het sleutels die in meerdere dimensies bestaan en de vorming van een roosterstructuur impliceren gemaakt van gelijke afstanden in de ruimte. De vraag is waar die punten zijn, en hoe dicht een bepaald willekeurig punt bij de coördinaten van een rooster is. In het hart is dit een rugzakprobleem in meer dan één dimensie.
” mijn huidige obsessie probeert erachter te komen hoe veilig deze op roosters gebaseerde dingen zijn, idealiter voordat we ze gebruiken om het internet te draaien, ” zegt Stephens-Davidowitz.,
” dit betekent dat we quantum-resistente cryptografie veel eerder nodig hebben dan we verwachten dat kwantumcomputers hun volledige potentieel bereiken,” zei Leo Ducas, onderzoeker bij het Centrum Wiskunde & Informatica in Nederland.
naast cryptografieonderzoek zijn het knapzakprobleem en zijn NP complete neven overal in het echte leven. Bijvoorbeeld, je hebt misschien gehoord van de” traveling salesman ” probleem, dat is ook NP compleet., De uitdaging hier is om de kortste route te vinden voor een verkoper om tussen een bepaald aantal steden te reizen alvorens terug te keren naar het startpunt. Nauw verwant is het voertuig routing probleem, waarbij meerdere voertuigen die leveringen.Luciana Buriol, universitair hoofddocent aan de Universidade Federal do Rio Grande do Sul in Brazilië, heeft dit probleem aangepakt om te proberen nieuwe benaderingen voor de gezondheidszorg te vinden., Ze werkte met een thuiszorgdienst waar artsen en verpleegkundigen patiënten in hun huizen bezoeken en hielp bij het optimaliseren van hun routes, gezien een beperkt aantal auto ‘ s beschikbaar zijn voor vervoer.
“gegeven 300 patiënten en 15 auto’ s, kunt u de oplossing niet vinden in een redelijke tijd,” zei ze. “Als je dagen hebt voor het uitvoeren van het algoritme zul je vinden — maar je moet vinden in minder dan 2 uur, anders zul je nooit gebruiken in de praktijk.”
geen enkel one-size-fits-all algoritme kan deze problemen oplossen., In plaats daarvan vindt Buriol snelle manieren om tot nuttige benaderingen te komen, zodat ze in actie kunnen worden gebracht.
Rugzakken overal om ons heen
voor degenen onder ons die geen computerwetenschapper zijn en in het echte leven met dit soort problemen worden geconfronteerd, hoe goed zijn we? Murawski ‘ s groep vindt voorlopige resultaten dat als je mensen rugzakachtige problemen geeft, we ook hevig worstelen., In kleine experimenten waarbij de deelnemers werden gevraagd om een rugzak op een computerscherm te vullen met items met aangegeven waarden en gewichten, hadden mensen de neiging om een moeilijker tijd te hebben om de inhoud van de rugzak te optimaliseren naarmate het aantal itemopties steeg—hetzelfde probleem dat computers hebben. De onderzoekers zeggen dat deze bevinding kan worden gerelateerd aan “keuze overbelasting”: de manier waarop we bevriezen wanneer gegeven te veel keuzes, zelfs in eenvoudige situaties zoals het kopen van jam in een supermarkt.
maar in de echte wereld redden we het wel. Aandacht is ook een rugzak probleem., Tijdens het rijden worden we geconfronteerd met een overvloed aan mogelijke afleidingen zoals vogels, wolken, de radio en omliggende gebouwen. We moeten alleen de meest relevante stimuli in onze mentale rugzakken stoppen—en in het algemeen doen we dat.
de vraag blijft: gezien het feit dat volledige NP-problemen moeilijker zijn voor computers dan andere soorten problemen, zijn ze ook moeilijker voor mensen? De beperkte eerste resultaten suggereren dat ze zouden kunnen zijn, die Murawski verrast.,
” als dit het geval blijkt te zijn, zou het suggereren dat de hardheid van dergelijke problemen een kenmerk van de problemen is—een eigenschap van de natuur—en niet in het oog van de toeschouwer,” Murawski zegt.