Zajímalo by mě --- jak se dokazuje, že něco nejde efektivně spočítat?
Může se to převést na NP-úplný problém a pak tomu věřit, že NP-úplné problémy nejdou řešit polynomiálně --- ale pokud např. problém nejde vyřešit polynomiálně v 90% případů a jde vyřešit v 10%, tak sice může být NP-úplný, ale šifrovací algoritmus, který jde v 10% případů rozlousknout, je na nic.
Nebo je to důkaz pouze částečný --- nejde to spočítat algoritmy skládajícími se z určitých operací?
Názor k článku
Vlastimil Klíma: Zcela nový koncept hašovacích funkcí
