Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od aaa - Nechapu. Co by jako mel "dukaz P/NP" dokazat?...

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

  • 13. 11. 2006 12:54

    aaa (neregistrovaný)
    Nechapu. Co by jako mel "dukaz P/NP" dokazat? Pride mi, ze tu nikdo moc nerozumi tomu, co je to P a co je to NP. Problem nalezeni kolize k hasovaci funkci je resitelny v linearnim case protoze obor funkcnich hodnot je konecny. Tak nevim co by mel byt jako ten NP-uplny problem.

    NP-uplnost je definovana nad !NEKONECNOU! mnozinout a problemu, ktery urcuje prislusnost do teto mnoziny. Tak napriklad, mnozina vsech grafu ktere lze obarvit 3mi barvami, je NP-uplna. (vsimnete si ze je nekonecna)

    A i kdyby, to ze je nejaky problem NP-uplny nemusi znamenat ze je "neresitelny". NP-uplny problem ktery resi algoritmus se slozitosti O(1.000000001^n) je "resitelny" mnohem lepe nez kdejaky problem v P.

    Co teda vlastne mame "P/NP dokazat"?