[math-fun] How difficult are math problems? The "Putnam."
It is hard to measure how "difficult" it is to solve mathematical problems. However, it occurs to me that Putnam exam questions are a somewhat standardized unit of mathematical difficulty. https://en.wikipedia.org/wiki/William_Lowell_Putnam_Mathematical_Competition Specifically, each year, the Putnam has 12 questions, each worth 10 points, to be solved in a total of 6 hours, i.e. 30 minutes per question. The questions are cooked up by experts with the intentional goal of making them so difficult that the median score on the exam (which is taken by good math undergraduate students Canada+USA-wide) is zero; but in such a way that the best 1% students in the country will score above about 42 points, and the best student in the country will score near 120. And this standard presumably is time-varying. Undergrads know different things now, than they knew in 1938. They as far as I know are not allowed to use electronic assistance on the Putnam, but perhaps one day that would/should be permitted, which if so would change things considerably. Pierre de Fermat presumably was considerably smarter than I, but he'd probably have no chance against me in a competitive math exam because he was so ignorant because math was just not very developed at that time. And some fans have been compiling online databases of all past Putnam problems. So consider 1 Putnam exam problem, as one "unit of difficulty." What, then, is the difficulty level of the hardest math problems that humanity has been able to solve? That 1 person has been able to solve? That you ever solved? Etc? It seems to me, if a problem requires solving about 5 sub-parts, each 1 Putnam difficulty, that's probably about the best I am capable of. It sort of grows on you exponentially. I mean, if I were given a Putnam problem, there is perhaps 50% chance I could solve it. (Depends how motivated I was, if I had a lot of motivation maybe 90%?) So anyhow, assuming the 50% figure, then if I had to solve 5 in a row to solve the uber-problem, presumably there would be about 1/32 chance I could. And then of course you'd have to figure out the 5 sub-parts. So in this sense, I'm not very smart. I mean, if an undergrad can solve something in 20 minutes, it wasn't all that hard. And if the best I can hope to do is equivalent to about 5 of that, not very impressive. Now we have the advantage of standing on the shoulders of giants, electronic assistants, and database searches to locate the previous works by the giants. Plus, there's the collaborative effect where, if the problem requires solving 10 Putnam-level subproblems, and some of them have already been solved by somebody else, then even though you could not have managed all 10 by yourself, you still might be able to do it. So then what is reachable? The "classification of finite simple groups" for example, is one of the hardest math problems that humanity has (allegedly) managed to solve, and certainly beyond the ability of any one human. How many Putnams of difficulty were involved? Hard for me to say. I would guess this is less than a KiloPutnam, but more than 50 Putnams? How soon do you think a computer AI will be able to compete on the putnam exam? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
And as far as I know there have sometimes been post-graduate level "competitive math exams" such as one where teams from Mathematica Inc, Maple Inc, etc were to solve a set of torture problems posed by Nick Trefethen within some time limit, using their SMP to help, then the results used to judge how good each SMP was. (I think Gosper and Wolfram were some of the team members and Mathematica was the winning SMP?) Maybe you all can tell us more about those competitions? Were they really fair? I mean, it might be that this competition was really more about the humans than about the SMPs, in which case it did not fairly judge those SMPs? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
I think this a great proposal for a significant and meaningful AI test, ie is it possible to write a program that solves Putnam problems by writing solutions for them that would pass muster with human judges. If it is possible, I'd think having AI interlocutors (collaborators?) for doing math research wouldnt be far off, because one could pose similar problems and let the AI try them, too. Doron Zeilberger already routinely talks about his computer as a collaborator but that isnt at all the same in my opinion, at least as far as I understand his research. I'd say the same thing about papers in Experimental Mathematics journals .... they heavily use computers as tools but not as a direct collaborators in English. On Saturday, February 6, 2016, Warren D Smith <warren.wds@gmail.com> wrote:
And as far as I know there have sometimes been post-graduate level "competitive math exams" such as one where teams from Mathematica Inc, Maple Inc, etc were to solve a set of torture problems posed by Nick Trefethen within some time limit, using their SMP to help, then the results used to judge how good each SMP was. (I think Gosper and Wolfram were some of the team members and Mathematica was the winning SMP?)
Maybe you all can tell us more about those competitions?
Were they really fair? I mean, it might be that this competition was really more about the humans than about the SMPs, in which case it did not fairly judge those SMPs?
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
On 09/02/2016 05:28, Dan Asimov wrote:
These problems were nothing like Putnam problems. They were mainly very hard problems in numerical analysis, to calculate various tricky things to something like 10 decimal places.
And they weren't aimed particularly at the makers of mathematical software, though of course lots of mathematical software was used to solve them. The contest spawned a rather nice book, called "The SIAM 100-digit challenge", by Bornemann et al. -- g
I didn't know there was a book, but here's a review of it: http://www.davidhbailey.com/dhbpapers/dhb-siam100-rev.pdf <http://www.davidhbailey.com/dhbpapers/dhb-siam100-rev.pdf> that is nice enough to repeat the challenge questions. (Looks as though the goal was 50 digits, not just 10.) —Dan
On Feb 9, 2016, at 10:27 AM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 09/02/2016 05:28, Dan Asimov wrote:
These problems were nothing like Putnam problems. They were mainly very hard problems in numerical analysis, to calculate various tricky things to something like 10 decimal places.
And they weren't aimed particularly at the makers of mathematical software, though of course lots of mathematical software was used to solve them.
The contest spawned a rather nice book, called "The SIAM 100-digit challenge", by Bornemann et al.
On 09/02/2016 18:35, Dan Asimov wrote:
I didn't know there was a book, but here's a review of it:
http://www.davidhbailey.com/dhbpapers/dhb-siam100-rev.pdf <http://www.davidhbailey.com/dhbpapers/dhb-siam100-rev.pdf>
that is nice enough to repeat the challenge questions.
(Looks as though the goal was 50 digits, not just 10.)
The goal was 10 digits for each of the 10 problems, hence "100-digit challenge". On most of them some of the contestants calculated a lot more than that. The book explains how to get 10k digits on nine of them. (The exception is the third problem, to find the norm of a certain linear operator on a Hilbert space. They found 273 digits of that after months of computation.) (The announcement said "If anyone gets 50 digits, I will be impressed". In the event, there were 20 teams with 100 correct digits and a few more with 99.) -- g
I never got Warren's original! There were also the Wester tests: http://math.unm.edu/~wester/cas/book/contents.html which, I believe, Macsyma consistently won. --rwg On 2016-02-08 20:28, Thane Plambeck wrote:
I think this a great proposal for a significant and meaningful AI test, ie is it possible to write a program that solves Putnam problems by writing solutions for them that would pass muster with human judges. If it is possible, I'd think having AI interlocutors (collaborators?) for doing math research wouldnt be far off, because one could pose similar problems and let the AI try them, too. Doron Zeilberger already routinely talks about his computer as a collaborator but that isnt at all the same in my opinion, at least as far as I understand his research. I'd say the same thing about papers in Experimental Mathematics journals .... they heavily use computers as tools but not as a direct collaborators in English.
On Saturday, February 6, 2016, Warren D Smith <warren.wds@gmail.com> wrote:
And as far as I know there have sometimes been post-graduate level "competitive math exams" such as one where teams from Mathematica Inc, Maple Inc, etc were to solve a set of torture problems posed by Nick Trefethen within some time limit, using their SMP to help, then the results used to judge how good each SMP was. (I think Gosper and Wolfram were some of the team members and Mathematica was the winning SMP?)
Maybe you all can tell us more about those competitions?
Were they really fair? I mean, it might be that this competition was really more about the humans than about the SMPs, in which case it did not fairly judge those SMPs?
-- Warren D. Smith
participants (5)
-
Dan Asimov -
Gareth McCaughan -
rwg -
Thane Plambeck -
Warren D Smith