Na dnešnej prednáške sme hovorili o tom, že prvočíselná veta hovorí, že $p_n\sim n\ln n$. (Resp. ukázali sme si, ako z Čebyševových nerovností odvodiť $an\ln n < p_n < bn\ln n$.) Vidno teda, že uvedený odhad nie je až o toľko horší ako prvočíselná veta - je tam navyše jeden logaritmus. Navyše sa zdá, že pre niekoho, kto ovláda Kolmogorovskú zložitosť, je ten dôkaz vcelku ľahký.
Asi aj človek, ktorý nevie nič o Kolmogorovskej zložitosti, by mohol byť schopný získať nejakú predstavu o čo v tom dôkaze ide. (Ja mám dojem z toho, čo som si prečítal, že zhruba viem, o čo v tom dôkaze ide - keby som mu chcel porozumieť poriadne, tak by som s ním asi musel stráviť o čosi viac času.) Navyše na tento predmet chodia aj nejaký informatici, aspoň niektorí z nich by mohli o Kolmogorovskej zložitosti možno niečo vedia z iných predmetov - tak aspoň pre nich by táto informácia mohla byť zaujímavá. Tak sem pridám nejaké linky a odkazy, kde by sa dalo prečítať niečo o tomto dôkaze:
- Lance Fortnow: Kolmogorv Complexity - je to hneď po Theorem 2.1.
- Začiatok kapitoly 9 v Uwe Schöning, Randall J. Pruim: Gems of Theoretical Computer Science
- Theorem 2.72 v Hromkovič: Theoretical Computer Science (Tento odkaz mám od Mareka Špana).
- Kolmogorov Complexity applications in Number Theory - cstheory.stackexchange.com