Képzeld el, hogy tolvaj vagy, aki egy múzeumi kiállítást rabol ki kínzó ékszerekből, geodéziákból és ritka drágakövekből. Új vagy ebben, szóval csak egy hátizsákot hoztál. A cél az, hogy megszabaduljon a legértékesebb tárgyaktól anélkül, hogy túlterhelné a táskáját, amíg el nem szakad, vagy túl nehéz lesz hordozni. Hogyan választhat a tárgyak közül, hogy maximalizálja a zsákmányt? Felsorolhatnád az összes tárgyat és a súlyukat, hogy kézzel oldd meg a választ., De minél több objektum van, annál inkább adóztatja ezt a számítást egy személy—vagy egy számítógép-számára.
Ez a kitalált dilemma, a “hátizsák probléma,” csoportjába tartozik matematikai problémák híres határait a számítástechnika. És a hátizsák problémája több, mint gondolatkísérlet. “Sok problémával szembesülünk az életben, legyen az üzleti, pénzügyi, beleértve a logisztikát, a konténerszállító hajókat, a repülőgépek betöltését — ezek mind hátizsákos problémák” – mondja Carsten Murawski, az ausztráliai Melbourne-i Egyetem professzora., “Gyakorlati szempontból a hátizsák problémája mindenütt jelen van a mindennapi életben.”
a kutatók egyszer kihasználták a probléma bonyolultságát számítógépes biztonsági rendszerek létrehozására, de ezeket most meg lehet repedni, mivel a problémát annyira jól tanulmányozták. Ma, mivel a technológia képes összetörni a zárak a digitális kommunikációs szövőszék a láthatáron, a hátizsák probléma inspirálhat új módon felkészülni, hogy a forradalom.
minden vagy semmi
a hátizsák probléma az “NP” problémák osztályába tartozik, amely a “nem-determinisztikus polinom időt jelenti.,”A név, referenciák, hogy ezek a problémák erő egy számítógép, hogy menjen át sok lépéseket, hogy a megoldásra, de a szám növekszik drasztikusan mérete alapján a forrásoktól—például a leltári tételek közül választhat, amikor a töltelék egy adott hátizsák. Definíció szerint az NP-problémák olyan megoldásokkal is rendelkeznek, amelyeket könnyű ellenőrizni (triviális lenne ellenőrizni, hogy egy adott elemlista valóban illeszkedik-e egy hátizsákba).,
“a probléma, amelyet a teoretikusok elkezdtek megvizsgálni, az volt, hogy egy adott feladat mennyire hatékonyan végezhető el számítógépen” – írja Keith Devlin a The Millennium Problems című könyvben. Például: Adott egy listát az 1 millió múzeum leletek a súlyok, valamint a monetáris értékek, valamint egy hátizsák korlátozott 25 kiló, egy számítógép kell végigmenni minden lehetséges kombinációt létrehozni az egységes egyik legjobban jövedelmező zsákmány. Határozatlan időre tekintettel a számítógép brutális erőt használhat az ilyen nagy esetek optimalizálására, de nem olyan időtávokon, amelyek praktikusak lennének.,
“úgy gondoljuk, hogy az egész Földet processzorokkal lefedheti, és az univerzum hőhaláláig futtathatja őket, és még mindig nem tudja megoldani ezeknek a problémáknak a megfelelő verzióinak viszonylag kis eseteit” – mondja Noah Stephens-Davidowitz, a kaliforniai Berkeley-i Simons Intézet Microsoft kutatója.
néhány NP-probléma, mint például a hátizsák példa, különleges tulajdonsággal rendelkezik: az 1970-es évek elején Stephen szakács és Richard Karp megmutatta, hogy számos NP-probléma átalakítható a formális logika egyetlen problémájává., Ezért, ha egy algoritmussal hatékonyan megoldható és ellenőrizhető, akkor mind megtehetik. Ez a tulajdonság az úgynevezett ” NP teljesség.”
a számítástechnika és a matematika egyik legmakacsabb kérdése az, hogy ezek az “NP” problémák, beleértve a hátizsákos problémát is, valóban különböznek-e a “P” problémáktól, azoktól, amelyeket meg lehet oldani az úgynevezett polinom időben. Ha P=NP, akkor minden olyan problémát meg lehet oldani, amelynek megoldásait könnyű ellenőrizni-mondja Stephens-Davidowitz. Tehát, ha ez az egyenlőtlenség továbbra is fennáll, az Általános hátizsák probléma mindig nehéz lesz.,
a dolgok titokban tartása
kriptográfiai kutatók szeretik azokat a problémákat, amelyeket a számítógépek számára nehéz megoldani, mert hasznosak a digitális üzenetek titkosításában. A Knapsack-problem-szerű biztonsági kódok ehhez nem hasznosak, mivel túl könnyen feltörhetők, de a probléma által inspirált bonyolultabb módszereket fejlesztik, és egy nap szerepet játszhat a számítástechnika következő generációjának túlszárnyalásában.,
egy korai Hátizsák stílusú titkosítási módszernél az egyik személy privát kulcsa azoknak a számoknak a listája, amelyekben mindegyik nagyobb, mint elődeinek összege. Cserék érintő személy használna egy nyilvános kulcs, amely úgy néz ki, véletlenszerű, de alkotja számok az első listából konkrét átalakítások alkalmazott. Például, ha a nyilvános kulcs , az “1, 0, 0, 1” továbbított üzenet kódolva lesz 2+0+0+5 = 7 (Mert 2*1=2, 3*0=0, 4*0=0, és 5*1=5). A kulcsok közötti konverziókban részt vevő titkos számok lehetővé teszik az eredeti üzenet bemutatását.,
ahhoz, hogy ez működjön, a számítógépnek azt is ki kell derítenie, hogy egy adott számot meg lehet-e írni a privát kulcsban lévő számok egy részhalmazának összegeként, ami könnyű hátizsák problémává válik. Ez hasonlít kitöltésével egy hátizsák, egy adag ilyen másképp méretű tárgyak — mint egy gyűrű, egy festmény, egy autó, egy ház — tudva, hogy nem a mást, miután ellenőrizte, hogy a gyűrű a festmény illik. Ralph Merkle és Martin Hellman kriptográfusok 1978-ban írták le ezt az elképzelést, de mások rájöttek, hogyan lehet feltörni az 1980-as évek elejére.,
A Magáninformációk a mai interneten gyakran nagy prímszámokat tartalmazó kulcsokat használnak, és bár a nagy számok faktorálása nehéz, nem gondolják, hogy ugyanabba az “NP complete” osztályba tartoznak, mint a hátizsák problémája. A számítógépes tudósok azonban már felkészülnek egy olyan jövőre, amelyben a kvantumszámítógépek gyorsan feloldhatják ezeket a kulcsokat.
a kvantumszámítógépek a kvantummechanika elveire támaszkodnak, amely szerint egy részecske nem egyetlen pozícióban helyezkedik el, hanem annak a valószínűsége, hogy sok különböző helyen van, hacsak nem rögzítik és nem mérik., Míg a normál számítógépek 0S-ben és 1s-ben kódolják az információkat, addig a kvantumszámítógépben minden “qubit” a részecskék tulajdonságaival kapcsolatos lehetséges állapotok széles skálájával rendelkezik. A kvantumszámítógépek nem lennének hasznosak az internet böngészéséhez vagy forgatókönyv írásához egy kávézóban, de soha nem látott energiát szabadítanának fel néhány típusú matematikai problémára. Sajnos ezek a matematikai problémák alkotják a modern kiberbiztonság alapjait.
“bizonyos értelemben nagyon szerencsétlenek voltunk” -mondja Stephens-Davidowitz., “Sikerült megnyugtatnunk az internet biztonságát azon kevés probléma keménységén, amelyek a klasszikus számítógépek számára nehéznek tűnnek, de a kvantumszámítógépek számára könnyűek.”
míg a kvantumszámítás még gyerekcipőben jár, egyes kutatók szerint lemaradunk a felkészülésben. 2016-ban az Országos Szabványügyi és Technológiai Intézet (NIST) új kvantum-rezisztens titkosítási módszereket sürgetett, tavaly 26 elődöntőt hirdetett meg. Az egyik ilyen típusú algoritmust rács alapú kriptográfiának nevezik., A számok használata helyett olyan kulcsokat használ, amelyek több dimenzióban léteznek, és egy olyan rácsszerkezet kialakulását foglalják magukban, amely egyenlő távolságra van az űrben. A kérdés az, hogy hol vannak ezek a pontok, és milyen közel van egy adott véletlenszerű pont a rács koordinátáihoz. A szíve, ez egy hátizsák probléma több dimenzióban.
“A jelenlegi megszállottságom megpróbálja kitalálni, mennyire biztonságosak ezek a rács alapú dolgok, ideális esetben, mielőtt az internetet futtatnánk” -mondja Stephens-Davidowitz.,
“ez azt jelenti, hogy kvantum-rezisztens kriptográfiára van szükségünk sokkal korábban, mint azt várnánk, hogy a kvantumszámítógép elérje teljes potenciálját” – mondta Leo Ducas, a Centrum Wiskunde kutatója & Informatica Hollandiában.
a kriptográfiai kutatásokon túl a hátizsákprobléma és az NP teljes unokatestvérei mindenütt megtalálhatók a való életben. Például, lehet, hogy hallott a “utazó ügynök” probléma, amely szintén NP teljes., A kihívás itt az, hogy megtaláljuk a legrövidebb utat az eladó számára, hogy egy adott város között utazzon, mielőtt visszatérne a kiindulási ponthoz. Szorosan kapcsolódik a jármű útvonal probléma, amely úgy véli, több jármű szállítások.
Luciana Buriol, a brazíliai Universidade Federal do Rio Grande do Sul docense megtámadta ezt a problémát, hogy új megközelítéseket találjon az egészségügyi ágazat számára., Dolgozott egy otthoni ápolási szolgáltatás, ahol az orvosok és ápolók látogasson betegek otthonukban segített optimalizálni az útvonalakat, mivel korlátozott számú autó szállítható.
“300 beteg és 15 autó után belátható időn belül nem lehet megtalálni a megoldást” – mondta. “Ha napjai vannak az algoritmus futtatására, akkor megtalálja — de kevesebb, mint 2 órán belül meg kell találnia, különben soha nem fogja használni a gyakorlatban.”
egyetlen egy méretre illeszkedő algoritmus sem tudja megoldani ezeket a problémákat., Ehelyett a Buriol gyors módszereket talál arra, hogy hasznos közelítéseket érjen el, így azok működésbe hozhatók.
hátizsákok körülöttünk
azok számára, akik nem számítógépes tudósok, és szembesülnek az ilyen típusú problémák a való életben, mennyire jók vagyunk? Murawski csoportja az előzetes eredményeket úgy találja, hogy amikor az embereknek hátizsákszerű problémákat adsz, akkor is erőteljesen küzdünk., Kis kísérletekben, amelyekben a résztvevőket arra kérték, hogy töltsenek ki egy hátizsákot a számítógép képernyőjén a megadott értékeket és súlyokat hordozó tárgyakkal, az emberek inkább nehezebben optimalizálták a hátizsák tartalmát, mivel a tételopciók száma nőtt—ugyanaz a probléma, mint a számítógépek. A kutatók szerint ez a megállapítás összefügghet a “választási túlterheléssel”: az a mód, ahogyan túl sok választási lehetőséget kapunk, még olyan egyszerű helyzetekben is, mint például a lekvár vásárlása egy élelmiszerboltban.
mégis, a Való Világban, megkapjuk. A figyelem szintén hátizsákos probléma., Vezetés közben a lehetséges zavaró tényezők, például a madarak, a felhők, a rádió és a környező épületek bőségszarujával szembesülünk. A mentális hátizsákjainkban csak a legmegfelelőbb ingereket kell elhelyeznünk—és Általában igen.
a kérdés továbbra is fennáll: tekintettel arra, hogy az NP teljes problémái nehezebbek a számítógépek számára, mint más típusú konundrumok, az emberek számára is nehezebbek? A korlátozott kezdeti eredmények azt sugallják, hogy lehetnek, ami meglepte Murawskit.,
“Ha kiderül, hogy ez a helyzet, azt sugallja, hogy az ilyen problémák keménysége a problémák egyik jellemzője—a természet tulajdonsága -, nem pedig a néző szemében” – mondja Murawski.