5
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – vzn Apr 12 '16 at 15:22
4
$\begingroup$

The first excerpt hints at Barrington's theorem. The second is probably about natural proofs.

$\endgroup$
  • $\begingroup$ it would be helpful to be more specific/ detailed how the very abstract thms are converted/ reduced to nearly everyday/ applied statements $\endgroup$ – vzn Apr 12 '16 at 15:14
  • $\begingroup$ Perhaps you can do that with your own answer. $\endgroup$ – Yuval Filmus Apr 12 '16 at 15:14
  • $\begingroup$ its not exactly clear to me how to do that, do not fully see what Aaronson has in mind even with cursory/ rough awareness of the thm constructions, its extremely "sketchy" :| $\endgroup$ – vzn Apr 12 '16 at 15:23
4
$\begingroup$

Scott Aaronson, in a comment on the blog post those came from, gives a reference for each of the theorems. I quote directly from his blog. The first: "Width-5 branching programs can compute NC1 (Barrington 1986); corollary pointed out by Ogihara 1994 that width-5 bottleneck Turing machines can compute PSPACE."

The second: "Natural proofs (Razborov-Rudich 1993); in particular Wigderson’s observation about natural proofs for discrete log."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.