patternMinor
What theorem are these? (from Scott Aaronson's blog)
Viewed 0 times
thesewhatareaaronsontheoremblogfromscott
Problem
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?)
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?)
Solution
The first excerpt hints at Barrington's theorem. The second is probably about natural proofs.
Context
StackExchange Computer Science Q#55453, answer score: 4
Revisions (0)
No revisions yet.