18
$\begingroup$

It's well-known that there are tons of amateurs--myself included--who are interested in the P vs. NP problem. There are also many amatuers--myself still included--who have made attempts to resolve the problem.

One problem that I think the TCS community suffers from is a relatively high interested-amateur-to-expert ratio; this leads to experts being inundated with proofs that P != NP, and I've read that they are frustrated and overwhelmed, quite understandably, by this situation. Oded Goldreich has written on this issue, and indicated his own refusal to check proofs.

At the same time, speaking from the point of view of an amateur, I can assert that there are few things more frustrating for non-expert-level TCS enthusiasts of any level of ability than generating a proof that just seems right, but lacking both the ability to find the error in the proof yourself and the ability to talk to anyone who can spot errors in your proof. Recently, R. J. Lipton wrote on the problem of amateurs who try to get taken seriously.

I have a proposal for resolving this problem, and my question is whether or not others think it reasonable, or if there are problems with it.

I think experts should charge a significant but reasonable sum of money (say, 200 - 300 USD) in exchange for agreeing to read proofs in detail and find specific errors in them. This would accomplish three things:

  1. Amateurs would have a clear way to get their proofs evaluated and taken seriously.
  2. Experts would be compensated for their time and energy expended.
  3. There would be a significantly high cost imposed on proof-checking that the number of proofs that amateurs submit would go down dramatically.

Again, my question is whether or not this is a reasonable proposal. Obviously, I have no ability to cause experts to adopt what I suggest; however, I'm hoping that experts will read what I've written and decide that it's reasonable.

$\endgroup$
  • 4
    $\begingroup$ This is an interesting proposal, but I cannot see any question in your post. Voted to close as not a real question. $\endgroup$ – Tsuyoshi Ito Jan 25 '11 at 3:24
34
$\begingroup$

Let me respond to your suggestion with a counter-suggestion: Why don't you try setting up a business, acting as a middleman between amateurs and experts? Amateurs pay to have their proofs evaluated. You find an expert and pay the expert to evaluate the proof, taking a cut of the money for your middleman role. Trying to run such a business is the most reliable way of finding out whether your idea is a feasible one.

$\endgroup$
  • 3
    $\begingroup$ that's a creative suggestions :) $\endgroup$ – Suresh Venkat Jan 27 '11 at 22:12
  • 2
    $\begingroup$ That would be like stackexchange with money. Why not? $\endgroup$ – Raphael Jan 28 '11 at 0:26
  • 4
    $\begingroup$ Alas, to turn reputation points into dollars! ;) $\endgroup$ – Daniel Apon Jan 28 '11 at 1:03
  • 6
    $\begingroup$ Why would such a business put itself out of business by affirming a correct proof, should one actually be submitted? And what to do with amateurs who do not understand why their proofs are wrong? $\endgroup$ – Andrej Bauer Aug 3 '11 at 11:55
  • 4
    $\begingroup$ @Andrej: The business won't put itself out of business by affirming correct proofs, unless it deliberately restricts itself to an extremely limited set of problems. As for amateurs who do not, or refuse to, understand why their proofs are wrong, the beauty of the system is that because money is involved, the amateur will either pay for additional attention or go away. The business need not (and indeed should not) guarantee that the amateur will accept the verdict of the expert, only that the expert will provide an expert evaluation. $\endgroup$ – Timothy Chow Aug 7 '11 at 3:01
39
$\begingroup$

I have some "real-world experience" in this nascent industry (and no, I'm not talking about my $200,000 offer to Deolalikar :-) )

In January, a software developer emailed me that he had an attempted proof of P≠NP, and that while he was almost sure there was an error, he couldn't find it. He asked if I knew any grad students who'd be willing to find the error for him in exchange for a few hundred dollars.

To give you some context: I get a proof of either P≠NP or P=NP in my inbox roughly once per month. Many of these emails go to a long list of complexity theorists (Cook, Karp, Fortnow, Sipser...); they often include religious or metaphysical ruminations as well as dark hints about academic conspiracies. (In one case, there were graphic death threats against me, which led to my contacting the police.) Virtually none of them acknowledge any possibility that the proof might be wrong, or that the author might have misunderstood the question. And when, back in grad school, I tried to correspond with the authors, I found all of them to be fervent believers in Churchill's maxim "never, never, never, never give up."

So the software developer's request really impressed me! This was the first time I'd ever seen a P≠NP proof accompanied by this level of self-awareness---both about the imposition being made on people's time and (more importantly) about the likelihood of error. As it happened, my PhD student Michael Forbes sent the author a beautiful, detailed report explaining the problems with his approach; the author thanked Michael and (I think! :-) ) paid up as promised.

So yes: for amateurs who want someone to examine their P vs. NP proofs (or similar work), I think paying a grad student a few hundred bucks is a great way to go. (Note that grad students are a much better choice than professors: not only do they have more energy and enthusiasm for such things, they also need the money more.) I wish more amateurs availed themselves of this option.

$\endgroup$
  • $\begingroup$ +1, really interesting! I didn't know that P vs. NP proofs are generated at that rate (once per month). Since the theorists and grad students sometimes read and report the problems with any such proof attempts, it'll be a good idea to keep a public database of "P vs. NP proof attempts and their problems." Polymath includes Deolalikar's attempt. In general, the provers' names must be kept anonymous, so long as they want so. $\endgroup$ – M.S. Dousti Aug 5 '11 at 8:04
  • 13
    $\begingroup$ there already is such a database, at least of the ones that get a bit more traction. It's maintained by Gerhard Woeginger: win.tue.nl/~gwoegi/P-versus-NP.htm $\endgroup$ – Suresh Venkat Aug 5 '11 at 8:07
  • $\begingroup$ @Suresh: Thanks a lot. I didn't come by that page. Maybe those theorists who receive so many wrong attempts should advertise it a bit ;) And, um, it lacks Michael Forbes report. $\endgroup$ – M.S. Dousti Aug 5 '11 at 8:15
  • $\begingroup$ @SadeqDousti: well that's why he asks people to email him. $\endgroup$ – Suresh Venkat Aug 5 '11 at 15:51
  • $\begingroup$ Wait. Alleged P vs NP proofs are generated once per month and Scott gets one in his inbox per month? That's quite an impressive ratio. $\endgroup$ – Zsbán Ambrus Oct 20 '13 at 9:50
31
$\begingroup$

For a few months at the end of my senior year of college and the beginning of my first year of graduate school I made $60/hour correcting an amateur's incorrect proofs of Fermat's Last Theorem. In this case the person was an academic in another field, so he had a reasonable understanding of the value of expert time. It was good experience all around, I made a thousand dollars at a time where I didn't have any other good sources of income, and he learned the errors he made in several drafts.

I think for people who are making a genuine effort and who are willing to pay good money, it shouldn't be hard to find qualified undergraduates or young graduate students who need some money.

$\endgroup$
  • 11
    $\begingroup$ I think this could be turned into very profitable start-up given the number of amateurs around the world who are trying to solve the P vs NP problem :) $\endgroup$ – Mohammad Al-Turkistany Jan 24 '11 at 15:29
  • 1
    $\begingroup$ I am going to change and accept Timothy Chow's. I hope you aren't offended...your answer is also very good and I up-voted it. $\endgroup$ – Philip White Jan 28 '11 at 1:33
24
$\begingroup$

One problem that I see with your suggestion is that most P vs NP not-proofs are not even false. In other words, they usually suffer from a failure of definition or specification that makes them impossible to either verify as true or show to be false. I'll refer you to my (shameless self-promotion alert!) caricature of the typical interaction between experts and the amateur P vs NP enthusiast: it's hard to see how introducing money into this discussion would improve it.

p.s the above caricature is based on watching trainwrecks on comp.theory: Timothy Chow might have more to say about this, since he often patiently attempts to engage such folk.

$\endgroup$
  • 1
    $\begingroup$ Maybe. I doubt that I would do it. but I might let my grad student do it :) $\endgroup$ – Suresh Venkat Jan 23 '11 at 1:30
  • 2
    $\begingroup$ @Suresh, that's a stunningly accurate reenactment of my memory of the PvsNP blog brouhaha this past fall. (Except that you wrote that in 2004!) $\endgroup$ – Daniel Apon Jan 23 '11 at 1:30
  • 3
    $\begingroup$ not my first rodeo :) $\endgroup$ – Suresh Venkat Jan 23 '11 at 1:31
  • 4
    $\begingroup$ Not to pick on Suresh, but I think his response will be the typical one to suggestions like these (whether they're worthwhile or not). That is: "Maybe. I doubt that I would do it. but I might let my grad student do it :)" For better or for worse, the status quo of generally ignoring P vs NP proofs until they (somehow) rise to the top of the pile already handles the needs of the community sufficiently. $\endgroup$ – Daniel Apon Jan 23 '11 at 1:44
  • 7
    $\begingroup$ @Suresh: If the expert charges per hour, then I don't think it matters whether the proof is "not even wrong." The amateur is basically hiring the expert for private TCS lessons. But you're right that if the amateur demands, "Find the mistake or my money back" then no sane expert will take up the offer. Even if the expert is lucky and the proof has a clear mistake, the amateur may not understand it or accept that it is wrong. $\endgroup$ – Timothy Chow Jan 27 '11 at 21:45
2
$\begingroup$

I remember going to a language conference around 1985 where the following exchange took place:

Speaker: The leaves of the tree are instances of a NP-complete problem, but are easy to solve by hand.

Me: If the instances are easy to solve, perhaps the problem is not NP-complete.

Speaker: I don't understand.


$300 seems like too little to charge. It pays for only an hour or 2 of time. Any proof that short has already been ruled out.

$\endgroup$
  • 2
    $\begingroup$ You sure have a huge time rate. The professors I know earn a low two-digit amount (€) per hour. $\endgroup$ – Raphael Jan 24 '11 at 10:50
  • 11
    $\begingroup$ @Rafael: Typical consulting fees professors charge businesses are at least 2 to 3 times their salaries per hour. Second, how many hours do you think it's going to take to find the flaw in a proof? Certainly to discover the flaw in the most recent serious proof took significant time (I'd estimate quite a bit more than 2 or 3 hours) from at least a dozen professors. Even at the low 2-digit amount, that would be a lot more than 300 dollars. And as a professor, am I supposed to accept 300 dollars for something which (who knows) may take me somewhere between 4 and 40 hours? That's quite a gamble. $\endgroup$ – Peter Shor Jan 24 '11 at 16:45
  • 7
    $\begingroup$ (cont) On the other hand, if somebody pays me by the hour to discover the flaw in their proof, they have no idea how much time it's going to take, and so might be reluctant to agree to this. Maybe it could be organized as a challenge: the first person to find the flaw gets a thousand dollars. $\endgroup$ – Peter Shor Jan 24 '11 at 16:52
  • 2
    $\begingroup$ Pay-by-hour is a usual model even for tasks that have no predefined duration, such as craft or software development. It needs, of course, trust and/or proper contracts. $\endgroup$ – Raphael Jan 25 '11 at 13:32
  • 2
    $\begingroup$ @Peter Shor: I don't like the idea of a challenge. If you look at it as a system, it might waist more total expert time spend on it. I think some form of auction of expert time or a system with reputation for experts based on the satisfaction of proof authors from responses they get from an expert might be a better if we think of it as a market design question. $\endgroup$ – Kaveh Aug 2 '11 at 5:47
1
$\begingroup$

Definitely not. We do not need yet another academia alternative. Certain people have already provided those alternatives, providing both amateur and professional researchers and society with false hopes of a high-tech future (I have a particular venue in mind but I'd rather not mention it).

The academic system was forged after centuries into what it is. I see attempts to skip the peer review system as simply "skipping the line". If an amateur researcher does not have the skill to understand why her proof is wrong, either alone or with some comments from reviewing, then there is a simple solution and that is that she must study the subject at hand harder. This is why educational institutions such as universities exist, to certify the knowledge of a certain person. If that person happens to be a genius that grasps the knowledge of the field instantly, fine, award that degree as soon as possible. But the vast majority must and should undergo training for their own sake and for the sake of society.

What would you think if this line of business was taken from mathematics and was put on medicine or another field where the consequences are more immediate? How long until an untrustworthy businessman on purpose alters the amateur papers so that they are hard to review or can fool the reviewer? Fooling the customers-amateur researchers is bound to happen, as with all businesses that rely on hard to get knowledge.

You can see that my point is that there are functional problems before even delving into the technical details. And since I am making an engineering argument, "programming" is a good example of what happens when amateurs are trying to do serious work with little or no training. The last thing any scientific community needs is the media glorifying the next "self-taught theoretical computer scientist who challenges the foundations of the whole scientific community from his garage", let alone a fragile science as ours, which still tries to get the recognition it deserves.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.