Zajímavé, jenom bych poopravil či spíše doplnil pár věcí.
Jestli se nepletu, výsledek je z loňského léta.
Problém z třídy NP může být i velmi jednoduchý, protože NP je nadmnožinou třídy P, tedy polynomiálně rozhodnutelných problémů. Autor článku pravděpodobně myslí spíše NP-úplný problém, který je určitým způsobem nejsložitější pro danou třídu problémů.
Problém rozhodnutí prvočíselnosti ale nebyl považován za NP-úplný, naopak byl kandidátem na problém, který není v P, ale zároveň není NP-úplný.
Ještě bych podotknul, že problém NP=P je stále otevřený a tedy může (i když je to velmi nepravděpodobné) platit i to, že i NP-úplné problémy jsou řešitelné v polynomiálním čase. Ale i v případě nerovnosti ještě může platit, že NP-úplné problémy jsou řešitelné v čase lepším než exponenciálním (avšak horším, než polynomiálním).
A ještě něco. Známé pravděpodobnostní algoritmy pro testování prvočíselnosti jsou (zatím) rychlejší, než je ten nový polynomiální. A protože při jednom běhu dává pravděpodobnost chyby 1/2, jeho opakováním k-krát lze chybu srazit až na 1/2 na k, což třeba pro k=100 je mnohem méně, než pravděpodobnost chyby hardware, na kterém výpočet běží.
Takže pro praxi tento výsledek neznamená příliš velkou revoluci, jeho důležitost je hlavně teoretická.
Polynomiální znamená omezený polynomem. Tedy existuje k takové, že od určitého n platí f(n)<n^k. Existují funkce, které rostou rychleji, než polynom, ale přitom pomaleji, než exponenciála. Třeba takové n^logn určitě nelze omezit pomocí polynomu (logn přeleze libovolně velkou konstantu), ale přitom je to jistě menší, než 2^n (protože n^logn = 2^((logn)^2)) a logn^2 roste jistě pomaleji, než n.
Nicméně, problémy, které mají složitost mezi polynomem a exponenciálou, nejsou přiliš obvyklé, z hlavy si na žádný přirozený nevzpomenu (diagonalizační technikou lze takový problém snadno vyrobit, ale bude uměle vytvořený bez nějakého zřejmého promítnutí do "skutečného světa").
K těm pravděpodobnostním algoritmům. Nevím, co je to ARCLP, ale třeba algoritmus založený na Fermatově větě má při odpovědi "složené číslo" spolehlivost 100%. Při odpovědi "prvočíslo" se s pstí 50% plete. Takže když budu tento algoritmus opakovat stokrát a budu stále dostávat odpovědi "prvočíslo", na konci budu mít pravděpodobnost 1/2^100, že se jedná o prvočíslo a pst 1-1/2^100, že jsem udělal chybu a je to číslo složené.
Algoritmus pracuje v čase O((logN)^3), kde N je vstupní číslo, tedy v čase kubickém vzhledem k velikosti vstupu.
