Taktiež vás postaršili, že ak sa nájde dôkaz známeho problému z teoretickej informatiky P = NP, internet padne na kolená? V tomto článku si rozoberieme čo je pravda, a čo skôr „novinárska kačica“.
Jak bylo na virtuální konferenci FOSDEM.
Jak je to s přístupností mobilního menu z klávesnice? Používáte odkazy “více” a “zde”? Znáte rozdíl mezi aria-label, aria-labelledby a aria-describedby? Je PDF strojově čitelný formát z pohledu zákona o přístupnosti?
Posledních pár let mě baví se zabývat bezpečností aplikací. Čistě technicky. A když člověk tyhle věci implementuje, dostane se k zajímavým problémům, které by ho ani nenapadly. A tak se stalo, že jsem se dostal k proxy. Jako slepý k houslím.
OMG
Nechápu, jak tento článek prošel přes editora, je to dost ostudná vizitka redakce a někdo by se měl vážně zamyslet.
“pričom x je fixné (a konečné!) číslo”
Každé číslo je z definice konečné, chtěl-li autor mermomocí explicitně specifikovat, jaká čísla jsou relevantní, mohl napsat “reálné.”
“do množiny NP patria všetky tie ostatné, pre ktoré polynominálny algoritmus nepoznáme”
To je špatně, NP je nadmnožina P (plyne přímo z definice, že jde o problémy řešitelné v polynomiálním čase nedeterministickým TS) a P=?NP je otázka, jde-li o nadmnožinu vlastní.
Re: OMG
Ahoj,
čo sa týka „konečných“ čísel, prívlastok bol pridaný čisto ako dovysvetlenie. Článok je určený aj pre menej zbehlých ľudí a nie každý musí vedieť že „nekonečno“ v bežnom kontexte číslo nie je. Okrem toho, existujú aj pojmy „kardinálne číslo“ či „hyperreálne číslo“, označujúce práve nekonečná.
S druhou vetou máš samozrejme pravdu, pôvodne som sa snažil vysvetliť NP vs. NP-hard vs. NP-complete, čo som ale škrtol aby som neodbiehal pridaleko od témy. No a pri škrtaní vzniklo toto. Napíšem editorovi nech to pozmení.
Re: OMG
Jo, vypadalo to jako kiks po úpravě, proto jsem psal, že to je primárně chyba editora/korektora.
Článku by asi prospělo vysvětlení vztahů mezi NP, NP-hard a NP-complete.
Re: OMG
Díky, tu větu s množinami jsem změnil, viz komentář autora.
Jinak si dovolím připomenout, že tohle není akademický text, ale článek pro širší publikum. Na slovíčkaření si tu nehrajeme.
Re: OMG
Právě proto, že je pro širší publikum, by neměl obsahovat takové zjevné chyby. Korektní vyjadřování není slovíčkaření.
Re: OMG
Chybu jsme opravili. O tom žádná.
Re: OMG
Tady se zastanu autora i redakce. Hodnocení typu „OMG“ mi v tomhle případě přijde rozhodně víc nekorektní a přehnané, než to, že si dovolil napsat „(a konečné!)“ – přesně sem díky tomu pochopil co tím myslel i když sem matematickou hantýrku dávno zapomněl. A to byl myslím v případě tohoto článku účel.
O(n^3) není až tolik
S obecným principem (polynom dostatečně velkého stupně by mohl stačit) souhlasím, ale zrovna O(n^3) není v kryptografii až tak moc – vždyť třeba u RSA se používají algoritmy, které šifrují a dešifrují v O(n^3). Pokud bychom měli algoritmus, ktrerý v O(n^3) spočítá privátní RSA klíč z veřejného, byl by na tom útočník asymptoticky stejně jako legitimní uživatel a zachránit by to mohly už jen konstanty. Což v situaci, kdy legitimní uživatel chce rychlou funkčnost na mobilu (omezené CPU a baterie) a útočník má k dispozici grid a čas třeba i několik let, by muselo znamenat fakt monstrózní konstanty. Navíc konstanty lze někdy „umlátit“, třeba pomocí FPGA nebo ASIC. Nebo pomocí GPU, pokud je algoritmus dobře paralelizovatelný.
A to jsem uvažoval RSA a ne třeba AES-128, který má řádově kratší klíče. U RSA se dnes doporučuje minimálně 2028b klíč (což je jen délka modulu, ne délka celého klíče), u AES-128 se používá 128b klíč. A v tomto světle by na tom nebyl až tak dobře ani AES-256…
Ale pokud to bude O(n^19), měl nevyplatilo by se to (z hlediska počtu operací) pro 128b klíče, u O(n^32) ani pro 256b klíče. (Ten exponent 19 by mohl být ještě o trochu menší, ale pak by nebyl celočíselný…) Samozřejmě, ještě hraje roli cena operace (tedy ony konstanty), ale v případě symetrické operace už dnes tyto operace pro known-plaintext bruteforce jsou dost levné (což chce i legitimní uživatel, aby kryptografie nepřinášela velkou režii) a nedal by se moc čekat průlom, který by zde útočníkovi pomohl.
NP vs. NP-complete
Základní sdělení článku OK, ale chtělo by si to po sobě více přečíst…
Pokud myslíte NP-úplný problém, pak souhlas. (Nebo aspoň o tom není známo, přesněji řečeno.) Ale tak, jak je to napsané, to není pravda. Nějaký problém vyřešit musíme, a určitě se vejde do třídy NP, dost možná i do nižší.
Proč je potřeba rozlišovat NP a NP-úplné problémy lze vidět kousek výše. Ve článku potřebujeme oba pojmy. Kdybychom všechny výskyty „NP“ nahradili za „NP-úplný“, opravili bychom sice výše uvedený úryvek, ale pak by byl zase problém tady:
Tady nemám problém s doslovným zněním (až na „TSL“, což asi mělo být „TLS“), ale ukazuje to, proč nelze míchat „NP“ a „NP-úplný“ do jednoho pojmu. Jak faktorizace tak diskrétní logatirmus jsou v NP, ale dost možná nejdou NP-úplné. To není snadné dokázat (kdybych to uměl, dokázal bych zároveň, že P≠NP), ale je tu pár vodítek. Oba problémy patří do BQP, protože je díky Shorovu algoritmu můžeme na kvantovém počítači vyřešit s určitou ohraničenou pravděpodobností úspěchu v polynomiálním čase. To u problémů, o kterých víme, že jsou NP-úplné, neumíme. A nejspíš ani umět nebudeme – NP-úplné algoritmy umí na kvantovém počítači řešit Groverův algoritmus, o kterém bylo dokázáno (zřejmě za podmínky P≠NP), že je optimální. Jenže Groverův algoritmus není polynomiální, dovede „jen“ s ohraničenou chybovostí prohledat N možností v O(sqrt(N)), tedy bruteforce původně v O(n^2) zkrátí na O(n^(n/2)).
Ono v tom článku není až tak podstatné, že faktorizace zřejmě není NP-complete, jen jsem chtěl ukázat, že článek zmiňuje jak třídu NP, tak NP-complete, a měl by pro obojí používat jiný pojem, jinak je to matoucí.