Comments:

I started to read the paper several days ago. Here, in contentiously-(self?)-updating manner, I'll note my thoughts about and paraphrase its main results. ### Style I like the Levin style, he writes a bit provocative phrases that looks, in the same time, incredibly truthful (at least for the author himself). Consider for example what he says about the invention of positional numeral systems and Quantum computers: > Archimedes made a great discovery that digital representation of numbers is exponentially > more efficient than analog ones (sand pile sizes). Many subsequent analog devices yielded > unimpressive results. It is not clear why QCs [quantum computers] should be an exception. There is something in common between writing styles of Russian mathematicians, consider for example, especially non technical, works of [Leonid Levin](https://en.wikipedia.org/wiki/Leonid_Levin), [Mikhaïl Gromov](https://en.wikipedia.org/wiki/Mikhail_Leonidovich_Gromov), and [Misha Verbitsky](https://en.wikipedia.org/wiki/Misha_Verbitsky). ### One-way function and the axiom of choice One-way functions and the axiom of choice deals with practical or conceptual (im-)possibility to solve [inverse problems](https://en.wikipedia.org/wiki/Inverse_problem) arising in Computer Science and Mathematics. ### Kolmogorov complexity and One-way functions Two primes $p$ and $q$ have almost the same [informational content](https://en.wikipedia.org/wiki/Algorithmic_information_theory) as their product $pq$. However, the [$p, q \mapsto pq$](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions) is much more easy to do than [$pq \mapsto p,q$](https://en.wikipedia.org/wiki/Integer_factorization#Prime_decomposition).
Sergey Kirgizov at 2018-10-23 07:28:20
Edited by Sergey Kirgizov at 2018-11-13 19:45:03

You comment anonymously! You will not be able to edit/delete the comment.

Please consider to register or login.

Use $\LaTeX$ to type formulæ and markdown to format text.
When you post something to which you hold the copyright you authorise us to do distribute this data across the scientific community. All data you give us will be freely available online. You can post any public domain content. Please see this page to learn more about us, Papersγ's terms of use and privacy policy.