From: pcw@access.digex.net (Peter Wayner)
Date: Sat, 23 Apr 94 18:38:41 PDT
To: cypherpunks@toad.com
Subject: No Subject
Message-ID: <199404240138.AA24229@access2.digex.net>
MIME-Version: 1.0
Content-Type: text/plain


> > I wonder if Jesus can create a number so large he can't factor it?


This is a trope on the old question of whether an all powerful God could
make something so big that even he couldn't move it. I.e Church/Rosser 
before they "conceived" of that theorem.

The question is whether there is any strict bounds on the complexity
of making rocks and moving rocks. I would think that making and moving
rocks is in the same complexity class. 

The effort to make a rock is undoubtably linearly related to the size
of the rock. At least in the asymptotic case. 
Here's an algorithm that proves it's linear.

  Make a small rock.
  Repeat until the size is big enough.

  Gravity will pull it together once the rock is big enough. So
  this proves that the cost is at least asymptotically linear. 

The effort to move a rock is also linearly related to the mass of 
the rock. F=ma. 

So we can see that these are in the same complexity class. That
means we can't really be sure whether he could make some rock that
was slightly bigger than he could move. The complexity theory really
isn't strong enough to solve it.

On the other hand, creating composite numbers with two large, relatively
equally sized prime factors is pretty easy to do in time linear to 
the number of bits. 

Factoring that number still requires time _exponentially_ proportional
to the number of bits.

So if the God had a finite  amount of effort available, (but still beyond 
the ken of mere mortals) then I think it is safe to say that he COULD create
numbers so big that even he couldn't factor them. 

Now what if God had a _countable_ amount of effort available? Then he should
be able to factor any number that he created. I think that this follows
from the same proof that shows that the rational numbers are countable. 

--Peter "I would build my Church/Rosser on this Rock" Wayner
{I keep trying to stop making this pun, but it keeps pulling me 
back in.}