(Update on alleged P NE NP proof: There are some issues with it. See these posts on Lipton's blog:
here
and
here and also see a Wikipedia site that (I think) Terry Tao set up
here.
)
I recently read the following:
(Backdrop the author had already defined p(n) to be the
number of partitions of n.)
NOTE I use ki where the actual quote uses k
_{i}. Looks better in html,
though I am sure a better htmler than I could handle this.
For a positive integer n let d(n) be the sum of the divisors of n. For example
d(4) = 1 + 2 + 4 = 7

d(1000)=1+2+4+5+8+10+20+25+40+50+100+125+200+250+500+1000 = 2340

d(1001)=1+7+11+13+77+91+143+1001=1344
Unlike the numbers p(n), the numbers d(n) are easy to compute.
There is a simple explicit formula for them. Namely, if
n=2^{k2}3^{k3} ... p^{kp}
then
d(n)=(2^{k2+1}1)((3^{k3+1}1)/2)...((p^{kp+1}1)/(p1))
They are assuming factoring is easy.
Or perhaps they are assuming you are given the number already factored.
There are no comments on what easy to compute might really mean,
though they seem to think that having a simple explicit formula implies
easy to compute.
To be fair, this book was written a while back before people in math really
took these notions seriously. The book is
Mathematical Omnibus: Thirty Lectures on Classic Mathematics
by Fuchs and Tabachnikov. Copyright 2007.
Disclosure: I got my copy for free in my capacity as SIGACT NEWS book review editor.

Posted By GASARCH to Computational Complexity at 8/11/2010 10:01:00 AM