Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Mikuláš Patočka - Jenomže potřebuješ mnohem silnější vlastnost, než je NP-úplnost...

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

  • 13. 11. 2006 4:26

    Mikuláš Patočka (neregistrovaný)
    Jenomže potřebuješ mnohem silnější vlastnost, než je NP-úplnost (i za předpokladu, že NP-úplné problémy řešit v polynomiálním čase nejdou)

    Příklad: problém, zda se program zastaví, nelze vyřešit (to je dokonce dokázáno) --- jenomže: když si nageneruješ z náhodných instrukcí program, tak z třeba z 99% případů ti spadne hned, čímž si dokázal, že se zastaví, a z 0.9% se zacyklí tak, že tok instrukcí nezávisí na obsahu paměti, čímž jsi dokázal, že se nezastaví --- a teprve u toho zbylého 0.1% začne být dokazování obtížnější.

    Takže máme sice matematicky dokázáno, že existuje program, u kterého nelze určit, zda se zastaví nebo ne, ale u 99,9% náhodně nagenerovaných programů to určit lze bez jakékoli duševní námahy.

    Matematika umí dokázat, že nějaká instance problému nejde řešit --- pro potřeby šifrování by bylo třeba dokázat, že žádná instance problému nejde efektivně řešit --- a není mi jasné, jak tohle dělat a zda to vůbec jde.