omlouvam se za anglictinu, ale nejsem si jisty, jake jsou ceske terminy :))
posledni odstavec se zabyva vztahem mezi tzv. worst-case hardness a average-case hardness. pro vetsinu problemu (napr. NP-uplne problemy batohu, obchodniho cestujiciho apod...) pouze plati, ze jsou tezke v nejhorsim pripade, a dokonce vime, ze nahodna instance (pri uniformnim pravdepodobnostnim rozlozeni) je jednoducha (s velkou pravdepodobnosti). pouze u nekolika malo uloh (lattice problems; ?mrizky?) se umi dokazat, ze jsou tezke i pro nahodnou instanci.
bohuzel kryptografie zalozena na mrizkach neni pro praxi prilis efektivni, takze se neprosadila oproti RSA, coz ale neznamena, ze takovy kryptosystem neexistuje.
Názor k článku
Vlastimil Klíma: Zcela nový koncept hašovacích funkcí
