Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od aaa - to ze je problem NP-uplny jeste neznamena ze...

Článek je starý, nové názory již nelze přidávat.

  • 13. 11. 2006 11:33

    aaa (neregistrovaný)
    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.