Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Jano - Vazeny pane, zkuste treba wikipedii. Patrne byste se...

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

  • 14. 11. 2006 13:59

    Jano (neregistrovaný)
    Vazeny pane, zkuste treba wikipedii. Patrne byste se dozvedel, ze prislusnost problemu do trid neni podminovana nejakou nekonecnosti. Zlozitost algoritmu je definovana jako pocet kroku klasickeho turingova stroje v zavislosti na delce vstupu (pouze 0 a 1). Samozrejme v realu nikdo netvori pravidla pro zakladni turinguv stroj, protoze bylo ukazano, ze libovolny pocitac (ne zrovna kvantovy - mluvime o deterministickych algoritmech :) urychluje vypocet "jen malo". Taky vstup nemusi byt pocitany binarne.

    V praxi tedy vezmeme problem (zadani transformace vstupu na vystup) a merime, kolik kroku algoritmus potrebuje na vypocteni teto transformace. Pokud existuje (deterministicky) algoritmus, kde vstup neni v mocniteli, je problem v P, jinak je v NP. Specialni tridou je NPC, kam patri algoritmy, kde staci najit P algoritmus pro jeden z nich a cela trida NP bude patrit do P.