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.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(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
d(n)=(2k2+1-1)((3k3+1-1)/2)...((pkp+1-1)/(p-1))
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.
I imagine they meant "the algorithm to compute this is not complicated", which is obviously true. Also, a lot of computations are used in proofs only.
ReplyDeleteFactoring *is* easy from an intuitive point of view. Using sieve-like methods to find factors dates back to Eratosthenes, and for small numbers this works great. Not to mention that the prime factorization is unique.
ReplyDeleteWhat makes factoring hard is the formal notion of complexity and specially the idea of the size of the input. In fact I use factoring as an example in class as an example of why the notion of the size of input vs size of numbers concept is so important.
It's almost like the Newtonian vs relativistic view of mechanics. The first view is limited but it took long distances (in our case large numbers) to truly recognize the difference.
Factoring is easy if you are a mathematician because there is a well-defined, terminating algorithm to factor. Since when do mathematicians care about the notion of polynomial time?
ReplyDeleteHow many scientists from MIT does it take to solve P / NP?
ReplyDeleteHow many scientists from MIT does it take change a light bulb?
How many scientists from MIT does it take to solve a millenium prize problem?
ReplyDelete200,000
My motto used to be “What would Grisha Perelman Do” WWGPD?
ReplyDeleteBut now it’s quickly and unexpectedly been supplemented by “What would V. D. NOT Do” WWVDND? or how NOT to solve a milleniyum prize problem!
BTW when is the next Update? Can I download it with my next Windows Update? Will I be forced to restart my brain each time after I glance through an updated pdf, like I’m forced to restart my computer after a Windows update?
WWVDND?
ReplyDeleteWhy in the world do people like you even bother to read academic blogs? Is it just to look for chances to be cantankerous?
Since when to mathematicians care about poly time.? Actually, for a while now.
ReplyDeleteNote that Terry Tao and William Gowers,
both Field Medalists, care about these things.
Another Fields medalist who cares about P vs. NP is Steve Smale. I couldn't say
ReplyDeletewhen he started caring about P vs. NP
but I would hazard a guess that it was
during the 1980s: in 1983 he published
a paper on the average-case complexity
of the simplex method. I should also
point out that he is one of the Ss in
the BSS model of computation --- a
computational model that
provides important analogues of the
P vs. NP question.