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“.
Jestli jste někdy řešili nasazování aplikace, asi víte, že všechno odladit může být celkem zdlouhavá záležitost. Dokážete si představit, že na to máte jen týden? Že je to nemožné? Není! Jde to a ani to nemusí být příliš složité.
Reportáž z virtuální konference FOSDEM. Minule jsem popsali Go room, dnes se věnujeme monitoringu a observability.
Mikrofrontendy jsou zajímavá adaptace konceptu microservices pro potřeby frontendového vývoje. Podívejte se, co to v praxi obnáší a proč jsme se v Seznam.cz rozhodli vyvinout náš vlastní microfrontend framework, Merkur.
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í.