3
$\begingroup$

I am new to this site, and have deleted a question I asked regarding a "proof" of the undecidability of P=NP as it was not considered on-topic. Doing what I should have done prior to posting, I looked through the meta and found that posts regarding proofs of such results, particularly when they come from "cranky" sources, are not welcome on the site.

However, I am interested in finding out about possible flaws in such attempts as a learning experience. Is there any way to format such a question to make it acceptable here, or on any SE site? Are general questions about "flaws" too open ended to fit the SE format?

$\endgroup$
18
  • 1
    $\begingroup$ For reference the question is here: cstheory.stackexchange.com/questions/18923 and the author of the argument doesn't seem to even understand what is the P vs. NP question or what is a proof. This is exactly the kind of crank work that is unwelcome on this site. Questions concerning the correctness of such claims about well-known open problems are off-topic here. $\endgroup$
    – Kaveh
    Sep 9, 2013 at 3:57
  • $\begingroup$ I personally think it is very unlikely to learn much (if anything) from such attempts by non-experts. As an analogy, you can learn as much from such attempts that you can learn from a 14 year old kid's attempt to send a rocket to the moon. If you want to learn complexity theory pick a good book like Arora and Barak and read it. $\endgroup$
    – Kaveh
    Sep 9, 2013 at 4:03
  • $\begingroup$ @Kaveh Thank you for your reply, and I take your point. The unfortunate truth is that often people are curious about many subject areas, but do not have enough time to study in-depth all the areas they are curious about, so "Get a book and learn it yourself" is unhelpful. If it were possible to rephrase the question so that it did not mention such a proof directly, but indirectly addressed a question I had about an argument made in such a "proof"-it still might not be on topic here if the question was not sophisticated enough per the FAQ. So I guess I could try it at the CS stack exchange? $\endgroup$
    – MattyZ
    Sep 9, 2013 at 4:48
  • 1
    $\begingroup$ See this post and its answers on Computer Science Meta. $\endgroup$
    – Kaveh
    Sep 9, 2013 at 4:53
  • 1
    $\begingroup$ ps: The sentences in the argument posted in your question doesn't even make sense. In other words, it is not even wrong, it is like: "Apple Orange Ladder, Honey Dwarf Moon. Therefore P vs. NP is undecidable." You are asking what is wrong with the argument but it doesn't even make sense. $\endgroup$
    – Kaveh
    Sep 9, 2013 at 4:56
  • $\begingroup$ @Kaveh I'm not sure that even the original author intended it as a "serious" proof. As a layperson with respect to theoretical computer science, I was interested in what exactly makes it bad. I'm sorry if this offends you in some way. I understand now that such questions are off topic. $\endgroup$
    – MattyZ
    Sep 9, 2013 at 5:07
  • $\begingroup$ :) Of course the "argument" doesn't offend me, I am simply saying its sentences doesn't even make sense. Clearly the person who has written it doesn't understand what is a mathematical argument and doesn't understand the technical terms he is using, it doesn't even reach the point that one needs any knowledge of TCS to see it is not even an argument. Putting aside the fact that the argument doesn't make sense, the claim is also clearly false: P vs. NP can be stated as a completely formal statement in the language of arithmetic, and is not different from any other mathematical statement. $\endgroup$
    – Kaveh
    Sep 9, 2013 at 5:10
  • $\begingroup$ @Kaveh I didn't suggest the argument would offend you, I suggested that my desire to learn about its flaws was somehow offensive. In any case, if from the point of one versed in the field it is "not even wrong" as you say, and it not being a serious proof anyways, it seems pointless to waste any further time with it. $\endgroup$
    – MattyZ
    Sep 9, 2013 at 5:19
  • 2
    $\begingroup$ btw on meta I feel we should have a higher tolerance for speculative questions: after all, the meta site is for discussions. This is for whoever downvoted the question. $\endgroup$
    – Suresh Venkat
    Sep 9, 2013 at 6:48
  • $\begingroup$ the question kaveh cited is already 404-zapped. was it by the same person asking this meta-question? best place to read about failed attempts by amateurs is the Woeginger page. but failed attempts by professionals seems quite very much on-topic to me! however there are related questions, such as on "known obstacles" etc.... $\endgroup$
    – vzn
    Sep 10, 2013 at 19:34
  • $\begingroup$ bitrex, sympathize with some of your sentiments, try TCS chat or cs chat $\endgroup$
    – vzn
    Sep 10, 2013 at 19:37
  • $\begingroup$ bitrex on further thought you really seem to have two questions (1) what questions on P vs NP could be on topic here, and (2) how can a question be phrased about whether a proof is correct? as for (2) kaveh gave a good link on that. as for (1) P vs NP is indeed a bit of a "3rd rail" topic here because of what might informally be called "crank magnetism" due to being relatively easy to comprehend but very hard to prove... there are many similar problems in mathematics. fyi this page has many links to se questions related to P vs NP in refs $\endgroup$
    – vzn
    Sep 10, 2013 at 21:07
  • $\begingroup$ also, kaveh reflexively insists the proof is a crank proof, but can that be said of all the papers on the woeginger list? from occasionally scanning it, it appears to me that some authors have fairly high reputations and established backgrounds, such as working as professors at universities, even having Phds etc... have myself have looked into some of the proofs.... the list is not worthy of heavy attn, but on the other hand it is arguably worthy of more than oblivious disregard/knee-jerk dismissal... $\endgroup$
    – vzn
    Sep 10, 2013 at 22:14
  • $\begingroup$ fyi, example of effort to dissect a proof, 1/2-yr chat analysis of the fukuyama proof, now listed on the woeginger page, dialog with the author. $\endgroup$
    – vzn
    Sep 10, 2013 at 22:23
  • $\begingroup$ other meta post with site policy on the issue, now locked, is it ok to ask about the correctness of preprints on crank-friendly topics $\endgroup$
    – vzn
    Sep 10, 2013 at 22:47

1 Answer 1

Reset to default
2
$\begingroup$

We've been burned many times by claims regarding P vs NP that turned out to be false. See this page for the complete list. Hence, we tend to have little patience for questions asking for clarification regarding yet another attempt.

The point is that any reasonable proof attempt will require a tremendous amount of background to even follow and appreciate. For example, there are a a few ways in which one is NOT allowed to prove a P vs NP statement, and a serious proof attempt will at least make some attempt to address this issue first. But to even understand the forbidden proof methods takes a lot of background reading (for example the Arora/Barak book).

So Kaveh is correct in asserting that while the P vs NP statement might be accessible to the layman, any claimed proof is unlikely to be.

$\endgroup$
7
  • $\begingroup$ Thank you for your reply. The page you link to is actually where I obtained the "proof" in question. In particular I was interested in the claim "We cannot accept the definition of the set NP purely in terms of its members having a property (a solution test in polynomial time) that we have no reliable mechanism to detect" which even as a layperson wrt theoretical computer science seemed dubious. In any event, I hope I have a chance at some point to do the background reading required to fully understand the terminology and issues involved. $\endgroup$
    – MattyZ
    Sep 9, 2013 at 7:16
  • $\begingroup$ @bitrex fyi the woeginger list is something of a semiofficial TCS community blacklist, referring to anything on the page is "professionally taboo/untouchable".... as for sureshs statement "we've been burned", its an rhetorical/editorial "we", because almost no professional researchers are willing to look at amateur proofs.... $\endgroup$
    – vzn
    Sep 10, 2013 at 19:38
  • 1
    $\begingroup$ Never heard of it being used as a blacklist. Am not even sure what that means. As far as I know, the goal of the page is to be comprehensive. $\endgroup$
    – Suresh Venkat
    Sep 10, 2013 at 20:49
  • $\begingroup$ right, its not officially acknowledged as a blacklist but basically functions in the same way, as this meta thread very clearly reveals, and many other interactions on the site & elsewhere can attest (and am not even suggesting this is out of line with professional community opinion/tendency outside of stackexchange). the poster apparently has a reasonable question about a paper on the list (I guess!), and is quickly shot down in flames. bzzzt! deleted! vaporized! dont even know what the original question is, never got a chance to read it... not the 1st question to this site on the list... $\endgroup$
    – vzn
    Sep 10, 2013 at 22:18
  • $\begingroup$ by the way, the list maintained by woeginger is definitely not intended/presented by the author as "claims regarding P vs NP that turned out to be false," that is a basic misunderstanding of its nature... it can be taken/strictly construed only as "claims that have not been verified". $\endgroup$
    – vzn
    Sep 10, 2013 at 23:37
  • 1
    $\begingroup$ a blacklist is very conspiracy-theory description of the situation, and is inaccurate. the list is not filtered and is flooded by cranky papers, so it's just a time waste. if a legitimate proof were to surface, it would make it through peer review. if someone had a legitimate proof attempt, that is specific enough to be plausible and is not obviously "caught" by the known obstacles (e.g. GCT is such an attempt, or rather program), that's also publication worthy and will make it through peer review. and that is why the list is a time waste $\endgroup$
    – Sasho Nikolov
    Oct 1, 2013 at 16:10
  • $\begingroup$ I think a question of the form "There is this proof attempt which has been debunked, but why? In particular, I don't get why conclusion X is invalid." has merit, as long as X is short (few people want to read long un-proofs). In that case, a focused question appears which can be answered properly, provided the asker does know some basics. If all these requirements are met, you are welcome to ask on Computer Science. $\endgroup$
    – Raphael
    Oct 14, 2013 at 7:35

You must log in to answer this question.

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