[Computational Complexity] Factoring in P ?

Expand Messages
• (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)
Message 1 of 1 , Aug 11, 2010
(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 ki. 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
1. d(4) = 1 + 2 + 4 = 7
2. d(1000)=1+2+4+5+8+10+20+25+40+50+100+125+200+250+500+1000 = 2340
3. 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=2k23k3 ... pkp then
d(n)=(2k2+1-1)((3k3+1-1)/2)...((pkp+1-1)/(p-1))
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
Your message has been successfully submitted and would be delivered to recipients shortly.