[Computational Complexity] Factoring in P ?
- (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 exampleThey 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.
- 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
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