2
$\begingroup$

I've read this, and also run into the unpleasant situation of having my proof that I wanted to get checked closed as "not constructive."

I realize that a lot of people consider P vs. NP a "crank subject." In my own mind, at least, I am not a crank, in the sense that I have some training in mathematics and am aware of what the difference between a correct and incorrect proof is. (See some of my old posts under my other profile if you need evidence that I'm not totally incompetent.)

My question is: Given that there are other proofs, including NP = coNP proofs that are trivially wrong (but good questions nonetheless), and that when CStheory.se was just getting started, they said that they might have CS.SE be a proof-checking site for proofs like the ones I seem generate...

What does the site consider to be the difference between an "acceptable" check-my-proof question and an unacceptable such question? (note, they even have a tag for check-my-proof)

Of course you know, my interest is in (finally!) having a venue other than comp.theory to try to get my P vs. NP proofs checked. I don't belong to any elite cliques TCS cliques, and no friends or colleagues that I know know a thing about any of this stuff. So although I realize that some people find P vs. NP attempts annoying, I am quite serious about suggesting that CS.SE should be a venue for proofs--even "crank-friendly" proofs.

Thanks for reading. Yes, this was part question and part my own opinion--I hope that is okay. I hope that moderators and others will decide to make CS.SE a home for a broader class of proof checks. Maybe there should be some sort of upper bound on the length of the proof? Or other constraints to prevent abuse of the system (e.g., 1 proof a month, maximum)?

(And for anyone who cares, I already realized that the proof I posted before was wrong or at least incomplete/inadequate.)

$\endgroup$
4
$\begingroup$

I don't remember anyone on csthoery suggesting that CS.SE should be a place for checking proofs. Any serious attempt of a solution for any long famous open problem in math is very unlikely to be a few pages long. The length would make posting asking for checking correctness of such solutions unsuitable for any SE site. It is like posing the code of say linux kernel in one post and asking people to find any security holes in it. It would be instructive to try to do that on say SO to see this attitude is not particular of computer science community. Checking any proof beyond a page or two is "too-broad" for SE sites. At the same time, most of these claimed proofs won't be of use to anyone expect the OP, so they are also "too-localized".

Now the question you have linked to about NP vs. coNP is not a claim of solving the problem. It is someone who knows he is missing something trying to understand what he is missing. These kind of questions often result from basic misunderstandings. I myself did ask such question when I was an undergrad. They are fine questions that students ask and I think asking them is completely fine on CS.SE. They are quite different from a "crank" trying to solve an open problem. There are several signs that are useful to distinguish these. The two simple ones are:

  1. they are honestly phrased as people trying to understand what they are missing,

  2. they are rather short, have a few points, and are easy to answer for an expert in complexity theory.

Compare such questions by students to say Deolalikar's attempt which had tens of pages and took top experts in the area several weeks working full-time to understand it. I think the difference is clear.


Let me add some note from my personal perspective as a junior researcher in complexity theory. In the following I use the word "crank" not as a derogatory term but to refer to people I would refer to as a "crank", and hopefully it would become clear what I mean by it by the end of this part.

First, the general advice to any person who seriously wants to work and solve a famous open problem: first solve simpler problems and get them a certificate of approval from the experts by publishing them in a reputable conference or journal. That would demonstrate that you understands the basics and worth the time of experts to be taken seriously. If you don't have any interesting result in complexity theory published in a reputable venue then you will not be taken seriously. The problem with "cranks" is that they are not ready to go through this process of gaining reputation among experts. If you want to solve P vs. NP but don't care about solving other simpler problems like say separating AC0[p] vs. TC0, NC1 vs. P, etc. (or worst do not understand these terms) then you are likely to be considered a "crank". What experts care about is progress in our understanding of the nature of efficient computation, not just solving some open problem for its own sake. On the other hand, a crank just wants to solve the open problem and is not interested in progress in our understanding of the nature of efficient computation. Let's say someone shows that SAT can be solved in 1000000000n^1000000000 without any improvement in our understanding of the nature of efficient computation. I don't think that is an acceptable solution to P vs. NP for any expert in complexity theory. Similarly if someone shows that SAT is not in P but it still might be in n^{lg* n}. Or say someone gives me an encrypted completely formal solution of P vs. NP which can be verified to be correct by decrypting and looking at a few bits. The reason complexity theorists and theoretical computer scientist care about P vs. NP is the expectation that it will lead to a significant improvement in our understanding of the nature of efficient computation. But "crank" doesn't understand this. To a "crank", P vs. NP is like a computer game that has only one level and he wants to finish the game. A "crank" is like someone who wants to win the gold medal for swimming in Olympics without demonstrating to anyone that he can swim.

If you are seriously interested in complexity theory, try attacking simpler problems, get good interesting results, and get them published in reputable venues. Eventually you will become an expert and experts will be ready to consider your attempt more seriously.

Let me add this: the same rules applies to experts, i.e. if an expert claims to have solved P vs. NP too often (i.e. more than once in her life time, maybe twice), she would be ignored after her first/second claim. There has been claims of solution for the problem by experts in the previous decades, the difference between such experts and a "crank" is that they know claiming to have solved P vs. NP brings with it the great risk of loosing almost all of their professional reputation among their peers and not to be taken seriously anymore, reputation that they have gained over years through painful work. Therefore an expert won't gamble it easily. On the other hand, a "crank" can go on claiming to have found a new solution or have fixed the problems with his solution every week, while the simple/trivial mistakes he made in previous attempts demonstrates that he lacks knowledge/capability to solve the problem.

$\endgroup$
6
$\begingroup$

See here and here for general discussions about check-my-proof questions. Enough said, I think.

Your questions really seems to be:

Can I post my P?=NP proof attempts here?

Sure you can, but be prepared to see them ignored, downvoted, or even closed. Why? Well, you have already been pointed here, but let me summarise/rephrase.

  • A person that can expect to solve P?=NP should be able to check their own proofs up to a level at which submission to conferences/journals makes sense.
  • A proof of either direction is probably very long and very complex (in its first version). Both kinds are unsuited for this platform.

Note that I don't disregard the possibility that a layman stumbles across a short and elegant proof. Those who say so are silly, imho. But it is very, very unlikely, given the apparent hardness of the problem. Therefore, most experts (those whom you want and need to read your attempts) will weigh their interests and not read your posts¹. Simple as that.

So such questions would most likely be dead weight for the site, and purging dead weight is what we do.

What you really need is partners in crime which stand in front of a whiteboard with you.


  1. Case in point: the cstheory.SE community summarily shoots down such posts, even though they are the experts.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .