This work is licensed under a
Creative Commons License.
|
Thursday, October 16, 2008
How Much is a Proof?
Posted by Lance
Back in our grad schools days, Noam Nisan told me he preferred incomplete proof write-ups in papers. By being forced to fill in the missing steps, he could really understand what was going on in the proof.I don't agree with Noam. I shouldn't have to struggle to figure out how the author went from point A to point B. I've spent far too many hours trying to understand the logical jump when the author says ``Clearly'' or ``Obviously''. On the other hand I don't want the authors to spell out every small algebraic manipulation either. And it's just completely infeasible to give a fully formal logical proof of even the simplest theorems.
So what level of proof should one give? As a general rule you should write for the reader. What would make it easier for him or her to understand your paper? When you leave out some details are you doing that because it would clutter your proof or because you are trying to save yourself some time. If it is the latter you do no one any favors.
Don't make assumptions of your readers. If you use a supposedly ``well-known'' technique, then either spell it out or make it clear what you are doing with a reference for those of us unfamilar with such techniques.
And how many times have you read ``the full details will appear in the final version'' where there are no later versions? Put those details in now. If you hit a proceedings page limit, have a full paper on the web with a footnote in the conference version pointing there.
If you do have a technically messy proof, the technicalities often overshadow the very pretty new ideas you needed for the proof. Be sure to also give a proof sketch that brings those ideas to light.
But mostly the Golden rule applies—Write your proofs as you would like others to write proofs for you.
7:24 AM
# 15 comments
-
Also, writing out proofs clearly and in full detail is often good for the authors themselves. I have seen many bugs at the exact point at which the authors wrote "clearly.." or "obviously..."
-
Golden rule might not work here: Noam Nisan can write proofs with gaps, but
Lance Fortnow can't!
-
The last SODA call for papers had some text in the call for papers to the effect that full details must be present, in the paper or in an appendix. I hadn't been a big fan of appendices in the past but I thought that was a good idea, as a way to force authors to write the full details up front as they should rather than only writing the extended abstract.
-
Why not have online discussions to better explain proofs and/or seek clarification from the proof authors?
Wouldn't this make more sense than trying to guess which parts of the proof readers will find difficult and that should be explained in more detail?
-
When I saw the title of this post, I thought it meant: "How much does a proof cost?", which is in fact an interesting question. For example, Lance may prove 100 theorems a year, and get paid 100k. So one proof costs 1k dollars. What's this number for an average graduate student?
-
I would guess that nobody proves 100 theorems a year.
In any case, Lance (and everyone else) does more than prove theorems. Lance teaches, gives talks, does service, writes expository articles (and blog posts), advises students, etc., etc.
In fact, a very low percentage of a professor's time is spent on research.
-
"In fact, a very low percentage of a professor's time is spent on research."
Please tell me that you aren't implying that a large percentage is spent on teaching.
-
The general advice in this post seems like a good thing to spread far and wide, at the very least through other conference CFPs...
Is there any intrade market for how many theorems someone will prove a year? or for when P vs NP will be (dis)proved?
-
Please tell me that you aren't implying that a large percentage is spent on teaching.
Umm, yes actually.
Regardless of how good a teacher someone is, they are spending at least 10 hours per week per course. I don't know how many hours they work per week, but let's peg this as 25% of their time.
For the record, I'd estimate 40% of a prof's time dedicated to "admin", which includes advising, departmental admin, grant writing, refereeing, etc.
That leaves 35% for research, which is not exactly low but is lower than one might expect.
-
The most challenging papers I had to read in tcs are the ones written by Leonid Levin (extremely concise) and by Peter Gacs (lengthy but still very complicated) ... at least they're challenging for good reasons :)
-
All authors, without exceptions, should write full detailed proofs. All statements in a published paper should be precisely and formally presented, accompanied with a full, formal, detailed proof.
Any other option is unprofessional: it doesn't serve any purpose. Reader might get lost; statements might have fatal mistakes; the actual statements of theorems might cause confusion; referees might be mislead, etc.
Not everybody can write in such a way. But to claim there's any benefit in unprofessional scientific writing is wrong.
-
Anon #9: IANAP, but I think you're pulling those numbers from nowhere. A professor who's taught the same course for years doesn't have to spend as much effort on it as one who's teaching it for the first time -- certainly some work has to be done, but there's no good reason it should be more than 1 + epsilon times (lecture hours) + (office hours).
And amount of time spent on admin stuff varies widely between professors -- it's a function of how many students they have, what kind of positions they hold within a department, and all sorts of other, less-quantifiable factors.
Plus, of course, these things are not mutually exclusive and in fact are often parallelizable -- thinking about research during office hours, for example, is a trivial task.
-
Wow, Anon#9 must do some amazing math. Even ignoring whether the percentages have any link to reality, according to this poster we are told that 25% is "a large percentage" and 35% is "a very low percentage".
-
Wow, Anon#9 must do some amazing math. Even ignoring whether the percentages have any link to reality, according to this poster we are told that 25% is "a large percentage" and 35% is "a very low percentage".
That's hardly a fair complaint, since large/low is obviously meant in comparison with popular conceptions rather than in absolute terms. Plus you are misquoting: 35% was described as "not exactly low but is lower than one might expect" rather than "very low".
I disagree with the precise percentages in that comment, but the underlying sentiment is not so wrong.
But to claim there's any benefit in unprofessional scientific writing is wrong.
I certainly agree, but people are good at rationalizing all sorts of misbehaviors. I've known of a few older professors who actually argued that it is good not to prepare too much for class, on the grounds that seeing how an expert works out the details from scratch is illuminating to the students (despite leading to a much less polished presentation). There's a little bit of truth to this, but it is mainly nonsense. The same is true for writing: there's some small benefit to being forced to reconstruct a poorly written argument, but it is outweighed by the enormous drawbacks.
-
I was not misquoting. Back when Anon#9 was Anon#6 they wrote "In fact, a very low percentage of a professor's time is spent on research." and when they continued as Anon#9 they gave that percentage as "35% for research".
Links to this post:
Weblog Home
Archives
