Imaginează-ți că ești un hoț jefuit un exponat de muzeu de tentantă de bijuterii, cristale și pietre rare. Ești nou la asta, așa că ai adus doar un singur rucsac. Scopul tău ar trebui să fie să scapi cu cele mai valoroase obiecte fără a-ți supraîncărca geanta până când se rupe sau devine prea greu de transportat. Cum alegi printre obiectele pentru a maximiza prada ta? Ai putea lista toate artefactele și greutățile lor de a lucra răspunsul de mână., Dar cu cât există mai multe obiecte, cu atât mai mult impozitarea acestui calcul devine pentru o persoană—sau un computer. această dilemă fictivă,” problema rucsacului”, aparține unei clase de probleme matematice celebre pentru împingerea limitelor calculului. Și problema rucsacului este mai mult decât un experiment de gândire. „O mulțime de probleme cu care ne confruntăm în viață, fie că este vorba de afaceri, finanțe, inclusiv logistica, nave container de încărcare, de încărcare a aeronavelor — toate acestea sunt rucsac probleme”, spune Carsten Murawski, profesor la Universitatea din Melbourne, în Australia., „Din perspectivă practică, problema rucsacului este omniprezentă în viața de zi cu zi.cercetătorii au profitat odată de complexitatea problemei pentru a crea sisteme de securitate computerizate, dar acestea pot fi acum crăpate, deoarece problema a fost atât de bine studiată. Astăzi, ca tehnologie capabilă să spulbere lacătele de pe războiul nostru de comunicații digitale la orizont, problema rucsacului poate inspira noi modalități de pregătire pentru această revoluție.
totul sau nimic
problema rucsacului aparține unei clase de probleme” NP”, care înseamnă ” timp polinomial nedeterminist.,”Numele referințe modul în care aceste probleme vigoare un calculator pentru a merge prin mai multe etape pentru a ajunge la o soluție, și numărul crește dramatic bazat pe dimensiunea de intrări—de exemplu, inventarul de elemente pentru a alege de la atunci când umplutura un rucsac special. Prin definiție, problemele NP au și soluții ușor de verificat (ar fi banal să verificăm dacă o anumită listă de articole se încadrează, de fapt, într-un rucsac).,
„problema la care au început să se uite teoreticienii a fost cât de eficient poate fi efectuată o anumită sarcină pe un computer”, scrie Keith Devlin în cartea The Millennium Problems. De exemplu: având în vedere o listă de 1 milion de artefacte de muzeu cu greutățile și valorile lor monetare și un rucsac limitat la 25 de lire sterline, un computer ar trebui să parcurgă toate combinațiile posibile pentru a genera cea unică cu cea mai profitabilă lansare. Având în vedere o perioadă nedeterminată de timp, un computer ar putea folosi forța brută pentru a optimiza cazuri mari ca acesta, dar nu pe intervale de timp care ar fi practice., „credem că ați putea acoperi întregul Pământ cu procesoare și să le rulați până la moartea termică a universului și încă nu reușiți să rezolvați cazuri relativ mici de versiuni adecvate ale acestor probleme”, spune Noah Stephens-Davidowitz, cercetător Microsoft la Institutul Simons din Berkeley, California.unele probleme NP, cum ar fi exemplul rucsacului, au o proprietate specială: la începutul anilor 1970, Stephen Cook și Richard Karp au arătat că o varietate de probleme NP ar putea fi transformate într-o singură problemă de logică formală., Prin urmare, dacă cineva ar putea fi rezolvat și verificat eficient cu un algoritm, toți ar putea. Această proprietate este cunoscută sub numele de ” completitudine NP. una dintre cele mai încăpățânate întrebări din informatică și matematică este dacă aceste probleme „NP”, inclusiv problema rucsacului, sunt cu adevărat diferite de problemele „P”, cele care pot fi rezolvate în ceea ce se numește timp polinomial. Dacă P=NP, atunci este posibil să rezolvăm orice problemă ale cărei soluții sunt ușor de verificat, spune Stephens-Davidowitz. Deci, dacă această inegalitate persistă, problema generală a rucsacului va fi întotdeauna dificilă.,
Păstrarea Lucruri Secrete
Criptografie cercetatorii au probleme in dragoste, care sunt dificil de calculatoare pentru a rezolva, deoarece acestea sunt utile în cripta digital mesaje. Codurile de securitate asemănătoare cu problema rucsacului nu sunt utile pentru acest lucru, deoarece sunt prea ușor de spart, dar se dezvoltă metode mai complicate inspirate de această problemă și pot juca într-o zi un rol în depășirea următoarei generații de calcul., într-o metodă timpurie de criptare în stil rucsac, cheia privată a unei persoane ar fi o listă de numere în care fiecare este mai mare decât suma predecesorilor săi. Schimburile care implică acea persoană ar folosi o cheie publică care arată aleator, dar este alcătuită din numere din prima listă cu transformări specifice aplicate. De exemplu, dacă cheia publică este, mesajul transmis „1, 0, 0, 1” va fi codificat ca 2+0+0+5 = 7 (pentru că 2*1=2, 3*0=0, 4*0=0, și 5 * 1=5). Numerele secrete implicate în conversiile dintre taste permit dezvăluirea mesajului original.,pentru ca acest lucru să funcționeze, un computer trebuie să-și dea seama dacă orice număr dat poate fi scris ca suma unui subset de numere în cheia privată, ceea ce devine o problemă ușoară a rucsacului. Este asemănător cu umplerea unui rucsac cu un lot de articole de dimensiuni diferite — cum ar fi un inel, un tablou, o mașină și o casă — și știind că nu poți să faci altceva după ce ai verificat dacă inelul și pictura se potrivesc. Criptografii Ralph Merkle și Martin Hellman au descris această idee în 1978, dar alții și-au dat seama cum să o spargă până la începutul anilor 1980., schimburile Private de informații de pe internetul de astăzi folosesc adesea chei care implică numere prime mari și, în timp ce factorizarea numerelor mari este dificilă, nu se crede că aparține aceleiași clase „NP complete” ca problema rucsacului. Cu toate acestea, informaticienii se pregătesc deja pentru un viitor în care computerele cuantice pot debloca rapid aceste chei. calculatoarele cuantice se bazează pe principiile mecanicii cuantice, care spune că o particulă nu este localizată într-o singură poziție, ci are probabilitatea de a fi în multe locuri diferite, cu excepția cazului în care este fixată și măsurată., În timp ce computerele normale codifică informații în 0s și 1s, fiecare „qubit” dintr-un computer cuantic ar avea o gamă largă de stări posibile legate de proprietățile particulelor. Calculatoarele cuantice nu ar fi utile pentru navigarea pe internet sau scrierea unui scenariu într-o cafenea, dar ar dezlănțui puterea nemaivăzută pe câteva tipuri de probleme de matematică. Din păcate, aceste probleme de matematică constituie fundamentele securității cibernetice moderne.
„într-un anumit sens, am avut cu adevărat ghinion”, spune Stephens-Davidowitz., „Am reușit să odihnim securitatea internetului pe duritatea unora dintre puținele probleme care par a fi grele pentru computerele clasice, dar ușor pentru computerele cuantice.în timp ce calculul cuantic este în fază incipientă, unii cercetători spun că suntem în urmă în pregătirea pentru aceasta. În 2016, Institutul Național de standarde și Tehnologie (NIST) a solicitat noi metode de criptare rezistente la cuantice, anunțând 26 de semifinaliști anul trecut. Un astfel de tip de algoritm dezvoltat se numește criptografie bazată pe zăbrele., În loc să folosească numere, folosește chei care există în mai multe dimensiuni și implică formarea unei structuri de zăbrele formate din puncte la distanțe egale în spațiu. Întrebarea este unde sunt acele puncte și cât de aproape este un punct aleatoriu dat de coordonatele unei rețele. În centrul său, aceasta este o problemă de rucsac în mai multe dimensiuni.
„obsesia mea actuală încearcă să-și dea seama cât de sigure sunt aceste lucruri bazate pe zăbrele, în mod ideal înainte de a le folosi pentru a rula internetul”, spune Stephens-Davidowitz.,
„Acest lucru înseamnă că avem nevoie de quantum-rezistent la criptografie mult mai devreme decât ne-am aștepta computer cuantic pentru a ajunge la potențialul lor maxim”, a spus Leo Ducas, cercetător la Centrum Wiskunde & Informatica în țările de Jos.dincolo de cercetarea criptografică, problema rucsacului și verișorii săi compleți NP sunt peste tot în viața reală. De exemplu, este posibil să fi auzit despre problema „vânzătorului călător”, care este, de asemenea, NP completă., Provocarea aici este de a găsi cea mai scurtă rută pentru un vânzător să călătorească între un anumit număr de orașe înainte de a reveni la punctul de plecare. Strâns legată este problema de rutare a vehiculului, care ia în considerare mai multe vehicule care fac livrări.Luciana Buriol, profesor asociat la Universidade Federal do Rio Grande do Sul din Brazilia, a atacat această problemă pentru a încerca să găsească noi abordări pentru sectorul sănătății., A lucrat cu un serviciu de îngrijire la domiciliu unde medicii și asistentele vizitează pacienții în casele lor și a ajutat la optimizarea rutelor lor, având în vedere un număr limitat de mașini disponibile pentru transport. „având în vedere 300 de pacienți și 15 mașini, nu puteți găsi soluția într-un timp rezonabil”, a spus ea. „Dacă aveți zile pentru rularea algoritmului, veți găsi — dar trebuie să găsiți în mai puțin de 2 ore, altfel nu veți folosi niciodată în practică.”
nici un singur algoritm one-size-fits-all nu poate rezolva aceste probleme., În schimb, Buriol găsește modalități rapide de a ajunge la aproximări utile, astfel încât acestea să poată fi puse în acțiune. Rucsacuri peste tot în jurul nostru pentru aceia dintre noi care nu sunt oameni de știință de calculator și se confruntă cu astfel de probleme în viața reală, cât de buni suntem? Grupul lui Murawski găsește rezultate preliminare că atunci când dai oamenilor probleme asemănătoare rucsacului, ne luptăm și cu putere., În experimente mici, în care participanții au fost rugați să umple un rucsac pe un ecran de computer cu elemente care transportă valorile și greutățile declarate, oamenii au avut tendința de a avea un timp mai greu optimizarea conținutului rucsacului ca numărul de opțiuni de elemente a crescut—aceeași problemă computerele au. Cercetătorii spun că această constatare poate fi legată de” supraîncărcarea alegerii”: modul în care înghețăm atunci când ni se oferă prea multe opțiuni, chiar și în situații simple, cum ar fi cumpărarea gemului la un magazin alimentar.cu toate acestea, în lumea reală, ne descurcăm. Acordarea atenției este, de asemenea, o problemă cu rucsacul., Când conducem, ne confruntăm cu o cornucopie a posibilelor distrageri, cum ar fi păsările, norii, radioul și clădirile din jur. Trebuie să punem doar cei mai pertinenți stimuli în rucsacurile noastre mentale—și, în general, facem.întrebarea rămâne: având în vedere că problemele complete ale NP sunt mai dificile pentru computere decât alte tipuri de enigme, sunt și ele mai grele pentru oameni? Rezultatele inițiale limitate sugerează că ar putea fi, ceea ce l-a surprins pe Murawski.,”dacă acest lucru se dovedește a fi cazul, ar sugera că duritatea unor astfel de probleme este o caracteristică a problemelor—o proprietate a naturii—și nu în ochii privitorului”, spune Murawski.