Představte si, že jste zloděj vykradl muzeum výstavu dráždivé šperky, geody a vzácné drahokamy. Jste v tom nový, takže jste si přinesli pouze jeden batoh. Vaším cílem by mělo být dostat pryč s nejcennější objekty, aniž by přetížení svůj pytel, až se zlomí, nebo se stává příliš těžké nést. Jak si vyberete mezi objekty, abyste maximalizovali svou kořist? Můžete uvést všechny artefakty a jejich závaží, abyste vyřešili odpověď ručně., Ale čím více objektů existuje, tím více zdanění se tento výpočet stává pro osobu—nebo počítač.
toto smyšlené dilema, „problém s batohem“, patří do třídy matematických problémů známých posouváním limitů výpočetní techniky. A problém s batohem je víc než jen myšlenkový experiment. „Mnoho problémů, kterým čelíme v životě, v podnikání, financí, včetně logistiky, kontejner, loď, nakládání, nakládání letadel — to vše jsou batohu problémy,“ říká Carsten Murawski, profesor na University of Melbourne v Austrálii., „Z praktického hlediska je problém batohu všudypřítomný v každodenním životě.“
vědci kdysi využili složitosti problému k vytvoření počítačových bezpečnostních systémů, ale nyní je lze popraskat, protože problém byl tak dobře studován. Dnes, jak technologie schopná rozbít zámky na naší digitální komunikaci tkalcovský stav na obzoru, problém batohu může inspirovat nové způsoby, jak se připravit na tuto revoluci.
Vše nebo nic
problém s batohem patří do třídy problémů „NP“, což znamená “ nedeterministický polynomický čas.,“Jméno reference, jak tyto problémy přinutit počítač, aby jít přes mnoho kroků, aby se dospělo k řešení, a počet se zvyšuje dramaticky v závislosti na velikosti vstupů—například soupis předmětů z čeho vybírat, když nádivkou konkrétní batohu. Podle definice mají problémy s NP také řešení, která lze snadno ověřit (bylo by triviální zkontrolovat, zda se konkrétní seznam položek ve skutečnosti vejde do batohu).,
“ problém, na který se teoretici začali dívat, byl, jak efektivně lze určitý úkol provádět na počítači,“ píše Keith Devlin v knize The Millennium Problems. Například: Vzhledem k tomu, seznam 1 milion muzeum artefaktů s jejich vah a peněžních hodnot, a batoh omezena na 25 liber, počítač by musel projít všechny možné kombinace, aby generovat jeden s nejvíce lukrativní trať. Vzhledem neurčitou dobu, počítač může použít hrubou sílu k optimalizaci velkých případech, jako je tento, ale ne na termíny, které by bylo praktické.,
„myslíme si, že může pokrýt celou Zemi s procesory a spustit je až do tepelné smrti vesmíru a stále nedaří vyřešit relativně malé instance odpovídající verze těchto problémů,“ říká Noah Stephens-Davidowitz, Microsoft Research Fellow na Simons Ústavu v Berkeley, Kalifornie.
některé problémy s NP, jako je příklad batohu, mají zvláštní vlastnost: na počátku 70.let Stephen Cook a Richard Karp ukázali, že různé problémy s NP mohou být přeměněny na jediný problém formální logiky., Pokud by tedy bylo možné vyřešit a efektivně ověřit pomocí algoritmu, všichni by mohli. Tato vlastnost je známá jako “ NP úplnost.“
Jeden z nejvíce tvrdohlavý otázky v informatice a matematice je, zda tyto „NP“ problémy, včetně problém batohu, jsou skutečně odlišné od „P“ problémy, ty, které mohou být řešeny v tzv. polynomiálním čase. Pokud P=NP, pak je možné vyřešit každý problém, jehož řešení lze snadno ověřit, říká Stephens-Davidowitz. Pokud tedy tato nerovnost přetrvává, bude obecný problém s batohem vždy těžký.,
Udržet Věci v Tajnosti,
Kryptografie vědci rádi problémy, které jsou obtížné pro počítač řešit, protože jsou užitečné při šifrování digitální zprávy. Batoh-problém-jako bezpečnostní kódy jsou užitečné pro to, protože jsou příliš snadno popraskané, ale složitější metody inspirované tento problém jsou vyvíjeny, a jednoho dne může hrát roli v vyzrál příští generace výpočetní techniky.,
v rané metodě šifrování ve stylu batohu by soukromý klíč jedné osoby byl seznam čísel, ve kterých je každý větší než součet jeho předchůdců. Výměny zahrnující tuto osobu by používaly veřejný klíč, který vypadá náhodně,ale je tvořen čísly z prvního seznamu se specifickými transformacemi. Například pokud je veřejný klíč, přenášená zpráva „1, 0, 0, 1“ by byla kódována jako 2+0+0+5 = 7 (protože 2*1=2, 3*0=0, 4*0=0, a 5*1=5). Tajná čísla zapojená do konverzí mezi klávesami umožňují odhalit původní zprávu.,
aby to fungovalo, musí počítač také zjistit, zda může být dané číslo zapsáno jako součet podmnožiny čísel v soukromém klíči,což se stává snadným problémem batohu. Je to podobné naplnění batohu dávkou takových různě velkých předmětů — jako prsten, obraz, auto a dům — a vědět, že nemůžete nic jiného po kontrole, že prsten a obraz se hodí. Kryptografové Ralph Merkle a Martin Hellman popsal tuto myšlenku v roce 1978, ale jiní přišli na to, jak rozlousknout od začátku roku 1980.,
Soukromé výměny informací na dnešním internetu často používají klíče zahrnující velkých prvočísel, a zatímco factoring velká čísla je obtížné, to není, aby si myslel, že patří do stejné „NP kompletní“ třídy jako problém batohu. Počítačoví vědci se však již připravují na budoucnost, ve které kvantové počítače mohou tyto klíče rychle odemknout.
Kvantových počítačů spoléhat na principy kvantové mechaniky, která říká, že částice se nenachází v jedné pozici, ale má pravděpodobnost, že v mnoha různých místech, pokud není přitlačen a měřit., Zatímco normální počítače kódují informace v 0s a 1s, každý „qubit“ v kvantovém počítači by měl širokou škálu možných stavů souvisejících s vlastnostmi částic. Kvantové počítače by neměl být užitečné pro prohlížení internetu nebo psaní scénáře v kavárně, ale že by se uvolnil nikdy-dříve-viděný výkon na několik typů matematických problémů. Bohužel tyto matematické problémy tvoří základy moderní kybernetické bezpečnosti.“v jistém smyslu jsme měli opravdu smůlu,“ říká Stephens-Davidowitz., „Podařilo se nám zbytek bezpečnost internetu na tvrdosti některé z mála problémů, které se zdají být těžké pro klasické počítače, ale pro kvantové počítače.“
zatímco kvantové výpočty jsou v plenkách, někteří vědci říkají, že jsme pozadu v přípravě na to. V roce 2016 vyzval Národní institut pro standardy a technologie (NIST) nové kvantově odolné šifrovací metody a loni oznámil 26 semifinalistů. Jeden takový typ vyvíjeného algoritmu se nazývá mřížková kryptografie., Namísto použití čísel používá klíče, které existují ve více rozměrech a zahrnují vytvoření mřížkové struktury vyrobené ze stejně rozmístěných bodů v prostoru. Otázkou je, kde jsou tyto body a jak blízko je daný náhodný bod k souřadnicím mřížky. Ve svém srdci je to problém s batohem ve více než jedné dimenzi.
„moje současná posedlost se snaží zjistit, jak bezpečné jsou tyto věci založené na mřížích, ideálně dříve, než je použijeme ke spuštění internetu,“ říká Stephens-Davidowitz.,
„To znamená, že potřebujeme kvantovou odolné kryptografie mnohem dříve, než očekáváme, že kvantový počítač, aby dosáhnout svého plného potenciálu,“ řekl Leo Ducas, výzkumný pracovník Centrum Wiskunde & Informatica v Nizozemsku.
kromě kryptografického výzkumu je problém s batohem a jeho úplnými bratranci NP všude v reálném životě. Například jste možná slyšeli o problému „cestujícího prodejce“, který je také kompletní NP., Výzvou je zde najít nejkratší cestu pro prodejce cestovat mezi daným počtem měst před návratem do výchozího bodu. Úzce souvisí s problémem směrování vozidel, který zvažuje více vozidel provádějících dodávky.
Luciana Buriol, docent na Universidade Federal do Rio Grande do Sul v Brazílii, napadl tento problém se snaží najít nové přístupy pro odvětví zdravotní péče., Spolupracovala s domácí pečovatelskou službou, kde lékaři a sestry navštěvují pacienty ve svých domovech a pomáhali optimalizovat jejich trasy, vzhledem k omezenému počtu automobilů dostupných pro přepravu.
„vzhledem k 300 pacientům a 15 vozům nemůžete najít řešení v rozumném čase,“ řekla. „Pokud máte dny pro spuštění algoritmu, najdete-ale musíte najít za méně než 2 hodiny, jinak nikdy nebudete používat v praxi.“
žádný jediný algoritmus s jednou velikostí se hodí pro všechny tyto problémy nevyřeší., Místo toho Buriol najde rychlé způsoby, jak dosáhnout užitečných aproximací, aby je bylo možné uvést do činnosti.
batohy všude kolem nás
pro ty z nás, kteří nejsou počítačoví vědci a čelí těmto druhům problémů v reálném životě, jak jsme dobří? Murawski skupina najde předběžné výsledky, že když dáte lidem problémy podobné batohu, bojujeme také mocně., V malé experimenty, v nichž byli účastníci požádáni, aby naplnit batoh na obrazovce počítače s předměty plnění uvedených hodnot a váhy, lidé mají tendenci mít víc času optimalizace batoh je obsah jako číslo položky možnosti zvýšení—stejný problém počítače. Vědci říkají, že toto zjištění může souviset s „přehlcení“: způsob, jakým jsme se zmrazit, když vzhledem k tomu, příliš mnoho možností, a to i v jednoduchých situacích, jako je nákup jam v obchodě s potravinami.
přesto se v reálném světě dostáváme. Věnovat pozornost je také problém batohu., Při jízdě čelíme hojnosti možných rozptýlení, jako jsou ptáci, mraky, rádio a okolní budovy. Do našich mentálních batohů musíme vložit pouze ty nejdůležitější podněty-a obecně to děláme.
otázkou zůstává: vzhledem k tomu, že úplné problémy NP jsou pro počítače obtížnější než jiné druhy hlavolamů, jsou pro lidi také těžší? Omezené počáteční výsledky naznačují, že by mohly být, což murawského překvapilo.,
“ Pokud se to ukáže, naznačuje to, že tvrdost takových problémů je rysem problémů-vlastností přírody-a ne v oku pozorovatele,“ říká Murawski.