Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This is my first post after being a passive user for some time now. I wish to ask some questions if I may. I am not a mathematician but my question relates to the field of maths/computer science. In particular, the P vs NP problem. I am aware that this is a problem that elite professionals have not yet been able to solve ...

Regardless, I would like to ask:

If a person who is neither a mathematician nor a programmer were to come up with a flowchart or a series of steps written in basic English that allegedly provides a solution to one of the P vs NP problem, would that be counted as 'proving' that P = NP .. in order to claim the Clays Institute prize :) ? Or is it a must for one to write the solution as mathematical proofs / computer program?

Thank you.

share|improve this question
9  
See this collection: win.tue.nl/~gwoegi/P-versus-NP.htm. You don't want to become one of them. –  Yuval Filmus Jan 3 '13 at 19:17
    
there is one possible "weak" precedent for this. Godels thm and diagonalization may have been loosely based on Richards paradox which was from literary work. but note it took extremely advanced mathematicians to convert it into legitimate mathematical statements/properties. –  vzn Jan 15 '13 at 17:22
    
@vzn: the very Wikipedia page you link to dates Richard's Paradox to 1905; diagonalization dates back to 1891. So Richard's Paradox is likely based on diagonalization, not the other way around. –  Niel de Beaudrap Mar 16 '13 at 12:02
    
@NieldeBeaudrap , vzn: Your comments were turning into a conversation so I moved them to chat, please continue there. –  Gilles Mar 18 '13 at 14:37

3 Answers 3

up vote 16 down vote accepted

"No", you can use "basic English".

If you succeeded, you would have created a constructive proof. Proofs in mathematics are often a mix of "basic English" as you call it and mathematical formulae, but they need not contain either to be a valid proof.

Suppose you have such a flowchart, what you need to prove—i.e. argue—is, that your algorithm works for every problem instance. The way you do that is entirely up to you, as long as the proof is unambiguous and all the premises you assert have been shown to be true.

Having done that, you have a mathematical proof in your hands. So really, I should have said "Yes" at the beginning, you do need a mathematical proof.

share|improve this answer
13  
Let's not give anyone false hopes here. It is extremely unlikely that a lay person can solve $P$ vs. $NP$, or that the solution could be expressed in "ordinary English". There are better things to do for a lay person than to try to solve the hardest math problems. –  Andrej Bauer Jan 3 '13 at 12:39
3  
@AndrejBauer Sure, I didn't mean to imply that it's likely. I assume that you would have liked an answer akin to Niel's better. But while it puts things into perspective well, it doesn't really address the question that was asked. –  phant0m Jan 3 '13 at 12:53
3  
I know you did not mean to imply anything like that. I just wanted to put down an explicit warning, lest a journalist or someone reads this and thinks $P$ vs. $NP$ will be resolved by a literary critic. –  Andrej Bauer Jan 3 '13 at 13:27
    
@phant0m: I'm curious. Does my first paragraph not address the actual question? –  Niel de Beaudrap Jan 3 '13 at 14:09
    
@NieldeBeaudrap Sure, it does address it, but it seems as if the conclusion needs to be inferred. Sidenote: One could also interpret the "Indeed" sentence as giving an explanation of a proof in words, but it in itself would not be a proof. Also, a turing machine in itself is not a proof, unless a proof of correctness is given. Also, it implies that presenting a TM over a flowchart is inherently superior as "proof", even when it's not. –  phant0m Jan 3 '13 at 15:47

A Turing machine, it must be remembered, is a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to P versus NP, most computer scientists would try to find a formulation of it which did come as close as possible to a plain english description in order to get as strong an understanding of the solution as possible.

But there is a fundamental problem with the sort of question that you're asking. What does it mean for someone who would be able to solve P versus NP — and by showing that they are equal, no less — to not actually be either a computer scientist or a mathematician? Perhaps they are not employed professionally as a computer scientist or mathematician, but this is beside the point if they have the skill to solve what some (Scott Aaronson, for example) describe as the most important mathematical problem we've ever considered. If someone has the training (or has even self-taught) to successfully tackle the problem, and also to clearly communicate the solution to others by identifying the major sub-routines and their roles in solving e.g. SAT or HAMPATH, then whether they are employed or even have degrees is an irrelevant detail; they are nevertheless in that case a mathematician or a computer scientist. Better still if they can describe how their solutions overcome classic obstacles such as oracle results, such as oracles A for which PANPA (or the opposite) by showing specifically what sorts of structure in the problem the algorithm takes advantage of, which would not be accessible in the oracle model. The problem, however, is that most people who dream of solving P versus NP as amateurs or outsiders seem to lack the communication skills to actually describe their work adequately, or (by virtue of not having read enough) they are unaware of results which would make their approach to solving the problem doomed from the start.

As with all dreams of glory these days, there is a basic problem with the fantasy of being the one to resolve P versus NP. The problem is that it's bound to be nearly impossible. Not actually impossible, mind you, or at least not necessarily impossible; just nearly so. As someone bright with ambition, it is possible for one to lose sight of the fact that there are many other bright people: many of whom have also thought about the problem; and many of whom are brighter than oneself, even by a couple of orders of magnitude. And that there have been such bright people for as long as the problem has been around; and yet it remains unsolved. Yes, it's possible in principle that everyone is thinking about it the wrong way, and have been for decades. But is that really particularly likely? Nobody should expect themselves to be the one person who can spot the one sign-error that everyone else is making, because if everyone else is making that error then there must be something about the problem that will lead one to make the same mistake. Or — in the more likely event that the reason why the problem remains unsolved is not that people keep making simple mistakes or haven't yet thought of the one simple trick that dissolves the whole thing — what makes the problem fundamentally difficult is essentially an objective difficulty of the problem, and no clever dancing steps will allow one to simply waltz gracefully past all obstacles; that what is required is an approach which is not merely novel, but quite profound, identifying subtle structures that there was good reason for nobody to have seen before. The sort of structure which one is most likely to spot by thinking continuously about the problem for years.

If you want to be realistic about what it would take to solve the P versus NP problem, you might compare it to similarly famous breakthroughs in the past few decades, such as the proofs of the four-colour theorem, Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive). There's no particular reason to suspect that P versus NP will be different; so that if in the end it is resolved by an amateur, chances are extremely strong that it would be by someone with similar background knowledge and awareness of techniques of someone who is academically trained. Any realistic amateur who dreams of solving P versus NP would do well to keep that in mind.

share|improve this answer
1  
While all you say is true, I fear that this mindset (which has become prevalent in the field, maybe as a protective mechanism) might discourage the one self-taught genius who might solve the problem today. I think a more helpful message is: go and get as much training as you need to convince even one professional, first to read your work and then of its validity. It might take years, but that's the way to go. –  Raphael Jan 14 '13 at 11:33
6  
@Raphael: I think that in fact my mentality is perfectly well-adjusted even to the possibility of a self-taught genius. My message to the self-taught genius is this: on the one hand, not being an academic does not mean that you're not a mathematician --- and that I would judge an answer by its quality. So the onus is on that self-taught genius to make sure that the answer has quality, and to be wary of the pitfalls that amateurs often fall prey to. –  Niel de Beaudrap Jan 14 '13 at 13:01
2  
I fear that this mindset... might discourage the one self-taught genius who might solve the problem today. — Good. Your self-taught genius should be reminded that the bar is extremely high and that dozens (hundreds?) of other self-taught geniuses have tried and failed to reach it. –  JeffE Jan 16 '13 at 5:45
    
"Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive)". this is a fair/reasonable expectation by some but on the other hand, unlike arbitrary theoretical curiosities like FLT and 4CT, a case can be made a P vs NP proof might yield (fundamental) tools for other complexity class separations and complexity theory in general, or could even be a rosetta stone or missing link for later advancement.. –  vzn Jan 23 '13 at 23:30
    
@vzn: I'm not really sure what you're getting at with that distinction. Just because P versus NP is important, doesn't make it any more likely that there exists find a simple solution that might be found by a clever but uninitiated amateur. –  Niel de Beaudrap Jan 24 '13 at 14:01

A proof that P = NP might get accepted by a mathematical journal, but it will never be accepted by the elite professionals. The reasons is that they know that P != NP (at least for all practical purposes). They also know that it is unbelievable difficult to prove this, so even a proof that P != NP will be received with a healthy amount of skepticism by the elite professionals.

The elite professionals have more elaborate reasons than that many bright minds tried and failed to construct a polynomial algorithm for NP or prove N != NP. However, they reasonably expect that this argument should be the most convincing for a layperson. They are probably right that reference to barriers related to relativizing proofs, natural proofs or algebrizing proofs are rarely convincing for a non-expert. If too many "amateurs" try to resolve P vs NP in a certain way (for example by logical resolution, or by reducing it to a linear programming problem), then somebody will go through the pain (this sometimes takes years) to prove that this specific angle of attack is likely doomed to fail.

Edit I'm delighted that this answer continues to attract (negative) feedback. Let me therefore replace the second part of the answer (which seems unrelated to the feedback, but may distract from the main point) by the following quote from Truth vs Proof:

We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed that in other sciences P != NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.

This change is not intended to reduce the amount of feedback, but to make it perfectly clear that this answer is serious about the fact that the experts "know that P != NP", even so they can't proof it.


23 Nov 2013 Thanks again for all the feedback. For the record, the answer now has 7 downvotes, 1 upvote and 14 comments (8 by me). Due to the amount of comments, interesting references and justifications given in the comments are hidden, so I decided to add some of them here:

  • As Gödel himself wrote to von Neumann, if P=NP were true "for all practical purposes", then his incompleteness theorem would only be true in theory, but effectively false in practice.

  • In his 1971 paper, Stephen Cook ... unable to produce counterexamples for the Davis-Putnam procedure (solved by Haken 1985). Today, many techniques, results and counterexamples are available for "disproving" proposed efficient NP-solvers. Also P = NP contradicts the "law of conservation of difficulty", the "qualitative infinitary <-> quantitative finitary" correspondence, ...

  • A long time ago, Scott Aaronson wrote this comment:

    anonymous: You claim (as being fact!) that 3SAT is a language in NP that cannot be computed in polynomial time. But you cannot prove it. Is that your scientific method? Yes. As a firm believer in science and reason, I strive to distinguish clearly between what I can prove and what I merely know is true.

  • Scott is famous for trying to demonstrate what it means that he "knows" something, for example by betting $200,000: scottaaronson.com/blog/?p=458

share|improve this answer
2  
Amateurs have produced many proofs of P=NP as well as P$\neq$NP. For that reason, "elite professionals" are unlikely to seriously consider efforts by amateurs. However, if a proof is correct, it will be accepted by "elite professionals". The result might not be relevant to the real world practitioners (indeed, I think that is going to be the case), but "professional" theoretical computer scientists will care anyhow. –  Yuval Filmus Jan 4 '13 at 1:11
6  
Nobody "knows" that P != NP. Experts may strongly believe it, but no expert knows it (unless somebody has a proof and kept it for himself/herself). It is possible, although unlikely, that P = NP is true. As a side-note, everybody (especially scientists) should be open to everything, unless proven otherwise. In this case every scientist, however large his belief is that P != NP, should accept that there is the possibility that P = NP holds. –  George Jan 4 '13 at 3:03
7  
In mathematics, the problem with ignoring proof and proceeding blindly forward is that you may assume something that is wrong. This will make the quest go much slower. The physical sciences don't have this problem (except for cases like quantum gravity/string theory) because they have to agree with experiment. –  Peter Shor Jan 5 '13 at 13:27
1  
@ThomasKlimpel: I remember posting that comment, but not where. Given that whomever I was responding to (you?) was simply using him as an authority to argue for the correctness of mathematical Platonism, whereas I have after some consideration arrived at a formalist position, the mere fact that Godel had a different opinion without further elaboration is indeed irrelevant. Technical arguments are not won as tennis matches are, with a swift rebuttal. Similarly, convincing answers are judged not solely by their concision (though that helps) nor by authority, but by their technical merit. –  Niel de Beaudrap Jan 14 '13 at 13:17
3  
@ThomasKlimpel In other sciences, we'd have observations to back up the hypothesis. In the case of P$\neq$NP, the only evidence we have is a lack of evidence (namely the fact that nobody has been able to come up with a polynomial-time algorithm for an NP-hard problem). I don't think other sciences would use a lack of observation as means to "prove" something; if you have never seen an apple detach from its tree, how can you claim it would (not) fall? –  Raphael Jan 14 '13 at 14:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.