wyobraź sobie, że jesteś złodziejem okradającym muzealny eksponat kuszącej biżuterii, Geodezji i rzadkich klejnotów. Jesteś w tym nowy, więc wziąłeś tylko jeden plecak. Twoim celem powinno być pozbycie się najcenniejszych przedmiotów bez przeciążania torby, dopóki nie pęknie lub nie stanie się zbyt ciężka do przenoszenia. Jak wybrać spośród obiektów, aby zmaksymalizować swoje łupy? Możesz wymienić wszystkie artefakty i ich wagę, aby wypracować odpowiedź ręcznie., Ale im więcej jest obiektów, tym bardziej opodatkowanie tego obliczenia staje się dla osoby – lub komputera.
ten fikcyjny dylemat, „problem plecaka”, należy do klasy problemów matematycznych znanych z przesuwania granic informatyki. A problem plecaka to coś więcej niż eksperyment myślowy. „Wiele problemów, z którymi borykamy się w życiu, czy to biznes, finanse, w tym logistyka, załadunek kontenerowców, załadunek samolotów — to wszystkie problemy z plecakami”, mówi Carsten Murawski, profesor Uniwersytetu w Melbourne w Australii., „Z praktycznego punktu widzenia problem plecaka jest wszechobecny w życiu codziennym.”
naukowcy kiedyś wykorzystali złożoność problemu do tworzenia komputerowych systemów bezpieczeństwa, ale teraz Można je złamać, ponieważ problem został tak dobrze zbadany. Dziś, gdy na horyzoncie pojawia się technologia zdolna do przełamania zamków w naszej cyfrowej komunikacji, problem plecaka może zainspirować nowe sposoby przygotowania się do tej rewolucji.
Wszystko albo nic
problem knapsacka należy do klasy problemów „NP”, co oznacza „czas nieokreślony wielomianu.,”Nazwa odnosi się do tego, jak te problemy zmuszają komputer do przechodzenia przez wiele kroków, aby znaleźć rozwiązanie, a liczba wzrasta dramatycznie w zależności od wielkości wejść—na przykład zapasów przedmiotów do wyboru podczas napełniania określonego plecaka. Z definicji problemy NP mają również rozwiązania, które łatwo zweryfikować (banalne byłoby sprawdzenie, czy dana lista przedmiotów faktycznie mieści się w plecaku).,
„problem, na który teoretycy zaczęli patrzeć, polegał na tym, jak wydajnie można wykonać konkretne zadanie na komputerze”, pisze Keith Devlin w książce problemy Milenijne. Na przykład: biorąc pod uwagę listę 1 miliona muzealnych artefaktów z ich wagą i wartościami pieniężnymi oraz plecak ograniczony do 25 funtów, komputer musiałby przejrzeć każdą możliwą kombinację, aby wygenerować pojedynczy z najbardziej lukratywnym łupem. Biorąc pod uwagę nieokreślony czas, komputer mógłby użyć brutalnej siły do optymalizacji dużych przypadków, takich jak ten, ale nie w ramach czasowych, które byłyby praktyczne.,
„uważamy, że można pokryć całą Ziemię procesorami i uruchomić je aż do śmierci cieplnej wszechświata i nadal nie rozwiązuje stosunkowo małych przypadków odpowiednich wersji tych problemów”, mówi Noah Stephens-Davidowitz, pracownik naukowy Microsoft w Simons Institute w Berkeley w Kalifornii.
niektóre problemy NP, takie jak przykład knapsack, mają specjalną właściwość: we wczesnych latach 70. Stephen Cook i Richard Karp pokazali, że różne problemy NP można przekształcić w jeden problem logiki formalnej., Dlatego, jeśli można rozwiązać i zweryfikować skutecznie za pomocą algorytmu, wszyscy mogą. Właściwość ta jest znana jako ” np kompletność.”
jednym z najbardziej upartych pytań w informatyce i matematyce jest to, czy te problemy „NP”, w tym problem plecaka, naprawdę różnią się od problemów” P”, tych, które można rozwiązać w tak zwanym czasie wielomianowym. Jeśli P = NP, to możliwe jest rozwiązanie każdego problemu, którego rozwiązania są łatwe do zweryfikowania-mówi Stephens-Davidowitz. Tak więc, jeśli ta nierówność będzie się utrzymywać, Ogólny problem plecaka zawsze będzie trudny.,
trzymanie rzeczy w tajemnicy
badacze kryptografii uwielbiają problemy, które są trudne do rozwiązania przez komputery, ponieważ są przydatne w szyfrowaniu wiadomości cyfrowych. Kody bezpieczeństwa podobne do plecaków nie są do tego przydatne, ponieważ są zbyt łatwo łamane, ale opracowywane są bardziej skomplikowane metody inspirowane tym problemem i mogą pewnego dnia odegrać rolę w przechytrzeniu następnej generacji komputerów.,
we wczesnej metodzie szyfrowania typu knapsack klucz prywatny jednej osoby byłby listą liczb, w których każda jest większa niż suma jej poprzedników. Wymiany z udziałem tej osoby używałyby klucza publicznego, który wygląda losowo, ale składa się z liczb z pierwszej listy z określonymi transformacjami. Na przykład, jeśli klucz publiczny jest, przesyłana wiadomość „1, 0, 0, 1” będzie zakodowana jako 2+0+0+5 = 7 (ponieważ 2*1=2, 3*0=0, 4*0=0, i 5*1=5). Tajne numery zaangażowane w konwersje między kluczami pozwalają na odsłonięcie oryginalnej wiadomości.,
aby to zadziałało, komputer musi również dowiedzieć się, czy dana liczba może być zapisana jako suma podzbioru liczb w kluczu prywatnym, co staje się łatwym problemem. Jest to podobne do napełniania plecaka porcją przedmiotów o różnej wielkości — takich jak pierścień, obraz, samochód i Dom – i wiedząc, że nie można włożyć niczego innego po sprawdzeniu, czy pierścień i obraz pasują. Kryptografowie Ralph Merkle i Martin Hellman opisali ten pomysł w 1978 roku, ale inni odkryli, jak go złamać na początku lat 80.,
prywatna wymiana informacji w dzisiejszym internecie często używa kluczy obejmujących duże liczby pierwsze, i chociaż faktoring dużych liczb jest trudny, nie uważa się, że należy do tej samej klasy „np complete”, co problem plecaka. Jednak informatycy już szykują się na przyszłość, w której komputery kwantowe mogą szybko odblokować te klucze.
komputery kwantowe opierają się na zasadach mechaniki kwantowej, która mówi, że cząstka nie znajduje się w jednej pozycji, ale ma prawdopodobieństwo, że znajduje się w wielu różnych miejscach, chyba że zostanie przypięta i zmierzona., Podczas gdy normalne Komputery kodują informacje w 0s i 1s, każdy „Kubit” w komputerze kwantowym miałby szeroki zakres możliwych stanów związanych z właściwościami cząstek. Komputery kwantowe nie przydałyby się do przeglądania Internetu lub pisania scenariusza w kawiarni, ale uwolniłyby niespotykaną wcześniej moc na kilku rodzajach problemów matematycznych. Niestety, te problemy matematyczne tworzą podstawy współczesnego cyberbezpieczeństwa.
„w pewnym sensie mieliśmy naprawdę pecha”-mówi Stephens-Davidowitz., „Udało nam się oprzeć bezpieczeństwo Internetu na twardości niektórych z niewielu problemów, które wydają się być trudne dla klasycznych komputerów, ale łatwe dla komputerów kwantowych.”
podczas gdy Informatyka kwantowa jest w powijakach, niektórzy badacze twierdzą, że jesteśmy w tyle w przygotowaniach do niej. W 2016 roku Narodowy Instytut Standardów i technologii (NIST) wezwał do nowych metod szyfrowania odpornych na kwanty, ogłaszając 26 półfinalistów w zeszłym roku. Jeden z opracowywanych algorytmów nazywa się kryptografią kratową., Zamiast używać liczb, używa kluczy, które istnieją w wielu wymiarach i obejmują tworzenie struktury kratowej złożonej z równomiernie rozmieszczonych punktów w przestrzeni. Pytanie brzmi, gdzie te punkty są i jak blisko dany losowy punkt jest do współrzędnych sieci. W jego sercu jest to problem plecaka w więcej niż jednym wymiarze.
„moja obecna obsesja próbuje dowiedzieć się, jak bezpieczne są te rzeczy oparte na kratkach, najlepiej zanim użyjemy ich do uruchomienia Internetu”, mówi Stephens-Davidowitz.,
„oznacza to, że potrzebujemy kryptografii kwantowej znacznie wcześniej niż spodziewamy się, że komputer kwantowy osiągnie swój pełny potencjał”, powiedział Leo Ducas, badacz w Centrum Wiskunde & Informatica w Holandii.
Na przykład, być może słyszałeś o problemie „komiwojażera”, który jest również np kompletny., Wyzwanie polega na znalezieniu najkrótszej drogi dla sprzedawcy do podróży między określoną liczbą miast przed powrotem do punktu wyjścia. Ściśle związany jest problem trasowania pojazdów, który uwzględnia wiele pojazdów dokonujących dostaw.
Luciana Buriol, profesor nadzwyczajny na Universidade Federal do Rio Grande Do Sul w Brazylii, zaatakowała ten problem, próbując znaleźć nowe podejście do sektora opieki zdrowotnej., Współpracowała z Służbą opieki domowej, gdzie lekarze i pielęgniarki odwiedzają pacjentów w ich domach i pomagały optymalizować ich trasy, biorąc pod uwagę ograniczoną liczbę samochodów dostępnych do transportu.
„biorąc pod uwagę 300 pacjentów i 15 samochodów, nie można znaleźć rozwiązania w rozsądnym czasie” – powiedziała. „Jeśli masz dni na uruchomienie algorytmu znajdziesz-ale musisz znaleźć w mniej niż 2 godziny, w przeciwnym razie nigdy nie użyjesz W praktyce.”
żaden pojedynczy uniwersalny algorytm nie rozwiąże tych problemów., Zamiast tego Buriol znajduje szybkie sposoby na uzyskanie użytecznych przybliżeń, aby można je było wprowadzić w życie.
wszyscy wokół nas
dla tych z nas, którzy nie są informatykami i borykają się z tego typu problemami w prawdziwym życiu, jak bardzo jesteśmy dobrzy? Grupa Murawskiego znajduje wstępne wyniki, że kiedy daje się ludziom problemy przypominające plecaki, my również walczymy z nimi potężnie., W małych eksperymentach, w których uczestnicy zostali poproszeni o napełnienie plecaka na ekranie komputera przedmiotami o podanych wartościach i ciężarach, ludzie mieli tendencję do trudniejszego optymalizacji zawartości plecaka, ponieważ liczba opcji przedmiotów wzrosła—ten sam problem mają komputery. Naukowcy twierdzą, że stwierdzenie to może być związane z „przeciążeniem wyboru”: sposobem, w jaki zamrażamy, gdy mamy zbyt wiele wyborów, nawet w prostych sytuacjach, takich jak kupowanie dżemu w sklepie spożywczym.
jednak w realnym świecie udaje nam się przetrwać. Zwracanie uwagi to również problem z plecakiem., Podczas jazdy napotykamy róg obfitości możliwych rozrywek, takich jak ptaki, chmury, radio i otaczające budynki. Musimy umieścić tylko najbardziej istotne bodźce w naszych umysłowych plecakach-i generalnie tak jest.
pozostaje pytanie: biorąc pod uwagę, że problemy z np są trudniejsze dla komputerów niż inne rodzaje zagadek, czy są też trudniejsze dla ludzi? Ograniczone początkowe wyniki sugerują, że mogą być, co zaskoczyło Murawskiego.,
„gdyby tak się okazało, sugerowałoby to, że twardość takich problemów jest cechą problemów—własnością natury—a nie w oku patrzącego” – mówi Murawski.