20
$\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.

Improve this question
$\endgroup$
1
  • 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, 2011 at 3:24

6 Answers 6

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ that's a creative suggestions :) $\endgroup$
    – Suresh Venkat
    Jan 27, 2011 at 22:12
  • 2
    $\begingroup$ That would be like stackexchange with money. Why not? $\endgroup$
    – Raphael
    Jan 28, 2011 at 0:26
  • 4
    $\begingroup$ Alas, to turn reputation points into dollars! ;) $\endgroup$
    – Daniel Apon
    Jan 28, 2011 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, 2011 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, 2011 at 3:01
42
$\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.

Improve this answer
$\endgroup$
5
  • $\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$
    – Sadeq Dousti
    Aug 5, 2011 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, 2011 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$
    – Sadeq Dousti
    Aug 5, 2011 at 8:15
  • $\begingroup$ @SadeqDousti: well that's why he asks people to email him. $\endgroup$
    – Suresh Venkat
    Aug 5, 2011 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, 2013 at 9:50
30
$\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.

Improve this answer
$\endgroup$
2
  • 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, 2011 at 15:29
  • 2
    $\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$
    – user1338
    Jan 28, 2011 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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Maybe. I doubt that I would do it. but I might let my grad student do it :) $\endgroup$
    – Suresh Venkat
    Jan 23, 2011 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, 2011 at 1:30
  • 3
    $\begingroup$ not my first rodeo :) $\endgroup$
    – Suresh Venkat
    Jan 23, 2011 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, 2011 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, 2011 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.

Improve this answer
$\endgroup$
6
  • 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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.