to ze je problem NP-uplny jeste neznamena ze je tezke ho vyresit. Co je horsi, slozitost O(1.00001^n) nebo O(n^100000)? Nedavno byl nalezen algoritmus, ktery overuje prvociselnost a je v P. Jenze slozitost toho algoritmu je neco kolem O(n^12), takze jeho prakticek vyuziti je v podstate nulove.
Zajimavy je napriklad dusledek: predpokladame-li ze P!=NP!=co-NP - coz je velmi pravdepodobne, problem overeni prvociselnosti je v P, problem overeni "neprvociselnosti" je taky v P a z toho by se dalo usuzovat, ze algoritmus na faktorizaci je taky v P.
Pro vysvetleni, je-li problem v NP, a mame-li instanci problemu I, muzeme k ni najit certifikat C. Platnost tohoto certifikatu muzeme overit v poly. case. Napriklad, Obchodni cestujici. Instance je nejaky konkretni graf a certifikat bude ona cesta. Overeni ze je cesta opravdu obchodni cesta (dale jen OC), je snadne. Jenze, jestlize grafem zadna OC nevede, jaky dame certifikat? Neexistence OC je totiz v co-NP. U prvociselnosti to ale neplati, tam je prvociselnost i neprvociselnost v P.
Takze, kdybych mel hadat, faktorizace je v P. Myslite si ze kdyz nekdo najde poly. alg. pro faktorizaci, ze rozbyje sifrovani verejnym klicem? Ja myslim ze ne, protoze ten algoritmus bude mit slozitost sice v P ale s tak velkym exponentem, ze v realu bude stejne nepouzitelny.
Odpověď na názor
Odpovídáte na názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí.
Pravidla pro diskutující
Přidáním čtenářského příspěvku do diskusí či fóra souhlasíte s tím, že budete dodržovat následující pravidla. Při jejich hrubém porušení se vystavujete riziku smazání příspěvku, jeho modifikaci, v krajním případě i zablokování přístupu do diskusí.
Redakce ze zásady nezasahuje do čtenářských diskusí a zavazuje se, že nebude mazat ani modifikovat příspěvky, kromě případů, kdy tyto porušují některé z následujících pravidel. V takové situaci je na zvážení redakce, zda příspěvek modifikuje s viditelným upozorněním, či přímo smaže. Redakce nikdy nemaže „nesouhlasné komentáře“ jen proto, že jsou nesouhlasné. Vítáme střet názorů, ale vždy v rámci slušné a kultivované debaty.
Příspěvky nesmí obsahovat:
- Vulgární či hrubé výrazy.
- Urážlivé výroky na adresu druhé osoby či skupiny osob.
- Texty, které mají za cíl jen vyprovokovat emotivní reakci (trolling).
- Rasové útoky či útoky na jakoukoliv jinou menšinu či skupinu obyvatel.
- Komerční nabídky a affiliate odkazy.
- Odkazy na warez, sériová čísla, licenční kódy, pornografii a další nevhodný materiál stejně jako žádosti o poskytnutí tohoto obsahu.
- Prokazatelně protiprávní obsah.
Informace o soukromí: U všech přidaných komentářů provozovatel ukládá IP adresu a hostname odesílatele. U neregistrovaných uživatelů se na webu zobrazuje část hostname, případně IP adresy, neumožňující identifikovat konkrétní počítač.
Povolené značky XHTML: a, br, code, em, li, ol, p, pre, strong, sub, sup, ul
