Kolmogorovská zložitosť a odhad pre $p_n$
Posted: Thu Oct 15, 2015 2:20 pm
Ako som sa dozvedel na minulej prednáške, tak pomocou Kolmogovskej zložitosti sa dá ukázať nejaký odhad na $n$-té prvočíslo, konkrétne sa dá zhora odhadnúť pomocou $n\ln^2n$; prípadne tam ešte pribudne nejaká konštanta. Alebo aj nejaký odhad pre $\pi(n)$. (Je fajn, že sa občas naučím aj ja niečo nové od ľudí, ktorým prednášam.)
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:
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