# What theorem are these? (from Scott Aaronson's blog)

Browsing Scott Anderson's blog, I found this list of theorem. Among them are:

If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging program; and a counter that could only be set to 1, 2, 3, 4, or 5, it would still be possible (given enough time) to carry out an arbitrarily long computation — just as if the memory weren’t being wiped clean each second. This is almost certainly not true if the counter could only be set to 1, 2, 3, or 4. The reason 5 is special here is pretty much the same reason it’s special in Galois’ proof of the unsolvability of the quintic equation.

It would be great to prove that RSA is unbreakable by classical computers. But every known technique for proving that would, if it worked, simultaneously give an algorithm for breaking RSA! For example, if you proved that RSA with an n-bit key took n5 steps to break, you would’ve discovered an algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took 2n^1/3 steps to break, you would’ve discovered an algorithm for breaking it in n(log n)^2 steps. As you show the problem to be harder, you simultaneously show it to be easier.

I learnt a bit of computer science in college, but I had never heard of these 2. I am very interested in knowing these. Any know what theorems are these? Thanks.

(since I can't comment...can you be more detailed about how "natural proof" do anything here?)

• from answers, these are apparently very deep/ advanced thms in CS that show up in Theoretical Computer Science typically not addressed at undergrad level. can provide some more detail in Computer Science Chat – vzn Apr 12 '16 at 15:22