Názor k článku Anonymita a analýza toku dát v p2p sieťach od anonym - A pri GDLP zase nenapcháte vstup na pásku...

A pri GDLP zase nenapcháte vstup na pásku Turingovho stroja v "krátkom zápise" (spor s definíciou náhody), GDLP musí byť reprezentované orákulom. Ak teda pridáme axiom "neexistuje náhodné orákulum" do teórie zložitosti, malo by z toho vyjsť, že pre každý konečný vstup musí existovať konečný algoritmus, ktorý rieši úlohu v polynomiálnom čase.

Po pridaní axiomu "neexistuje náhodné orákulum" pre každý problém s konečným vstupom (dĺžka ohraničená nejakou konštantou n) dokážeme vytvoriť algoritmus s konečným popisom, ktorý ho rieši v polynomiálnom čase (trápne zakódujeme všetky odpovede do stavov pre všetky možné vstupy, napr. ako haštabuľku). Problémy, ktoré boli nepolynomiálne vo svete s náhodným orákulom, budú polynomiálne tu, pretože zakódovanie ich vstupu je také dlhé ako samotný problém.

BTW, keď tak moje úvahy ignorujte alebo mi tam nájdite chybu ;-)