Jump to content

Talk:P versus NP problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 75.57.241.73 (talk) at 20:16, 8 September 2010 (→‎Narendra Chaudhari and links). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Vinay Deolalikar's proof

Please see Vinay Deolalikar and the discussion below Talk:P_versus_NP_problem#Potential_Solution

Consequences of proof

The statement "Firstly, it would change geopolitics, particularly the economy, national security, modern warfare, and intelligence. P being proven to equal NP means that no data encryption method is unbreakable, no matter how sophisticated, given enough computational resources and time." is incorrect on several grounds.

First, P == NP might not have any practical consequences at all (if proof is non-constructive, or the polynomial order is too high). For example, the method shown in "primes is in P" is not used in practice, to my knowledge.

Second, even if P==NP and an efficient method is found, several types of encryption remain safe:

  • One time pads, since any answer is as likely as any other. P==NP cannot help with this.
  • Quantum encryption, which depends on QM and not on computation.

Third, the statement "no data encryption method is unbreakable, no matter how sophisticated, given enough computational resources and time" is true whether P==NP or not.

There is no need to exaggerate - "stunning practical consequences" is already enough. LouScheffer (talk) 15:05, 19 May 2010 (UTC)[reply]

  • A lay reader would not infer security implications from "stunning practical consequences", as practicality and security aren't even distantly semantically related.
  • Even if there are new cryptographic techniques which negate any impact of an efficient method being found, existing data security strategies won't abandon the old and insecure techniques overnight. Many of these encryption techniques are hardwired into chips in essential equipment, such as televisions, cars, hospital equipment, and ATMs. Such a sudden, enforced exodus would break many information systems.
  • There are too many papers that discusses the relationship between the P versus NP problem and cryptography for the issue of cryptography being entirely left out of the P versus NP article. Stephen Cook's manuscript which is cited a couple times in this article is one of them (see page 9). It seems biased, even if the body of literature is really stretching the issue, that the topic is ignored altogether. The history of this mathematical area is significant, and worth knowing.
  • With any extremely powerful tool--as another example, fire--comprehensive reference sources should not, through omission, imply that no one has thought they might be dangerous, especially when many people have. It's also true that scientists and mathematicians (and everyone else, for that matter) are wrong all the time. Perhaps P versus NP won't have any negative consequences, but to not even consider them in something considered to be so powerful is highly foolish. In an encyclopedia, to not even mention the discussion in the literature is negligent.

67.240.173.68 (talk) 16:29, 19 May 2010 (UTC) Joe[reply]

It's very reasonable to mention that a constructive and efficient solution to certain NP-complete problems would break many existing cryptosystems. But that's about as far as you can go without exaggerating. LouScheffer (talk) 18:13, 19 May 2010 (UTC)[reply]
By definition, an efficient solution to any NP-complete problem is an efficient solution to every NP-complete problem. However, while finding a polynomial solution to an NP-complete problem would prove (by example) that P == NP, the converse is not necessarily true. More importantly, though, the most commonly used encryption protocols are not based on NP-complete problems, but on integer factorization and discrete logarithms. I say protocols and not algorithms, because these systems usually combine multiple algorithms: asymmetric-key algorithms based on factorization or logarithms are used to authenticate the parties and exchange randomly generated session keys, while the data itself is encrypted with symmetric-key algorithms using the aforementioned session keys. DES (talk) 11:42, 9 August 2010 (UTC)[reply]
That's "by definition" only in the technical sense that equates efficient with polynomial time. On the face of it it's not impossible that you could find a practical solution to some problem X that's formally NP-complete, but such that the reductions of the problems we actually want to know about to X, though polynomial time, are not practical. --Trovatore (talk) 17:50, 9 August 2010 (UTC)[reply]

Additional of a practical example

I suggest you add the following practical explanation of the problem by the Clay institute itself: http://www.claymath.org/millennium/P_vs_NP/ 

(attributing the copyright, of course)

The explanation does make things extremely more simple and clarifies the concept for non-mathematicians which is definitely a subgroup of people that this site is targeting. —Preceding unsigned comment added by Lyzazel (talk • contribs) 20:20, 19 June 2010 (UTC)[reply]

Attributing the text does not allow us to copy it wholesale. Fair use only extends to short quotations. See Wikipedia:Quotations#Fair use. Dcoetzee 09:12, 8 August 2010 (UTC)[reply]

Potential Solution

A proof to the P vs NP problem written by Vinay Deolalikar (HP Labs) is currently circulating the internet, awaiting confirmation as he released it on the 6th of August. Is this worth inclusion in the article at this point? —Preceding unsigned comment added by 24.81.111.60 (talk) 08:05, 8 August 2010 (UTC)[reply]

Feel free to add such a section. dcoetzee was referring, I think, to a published paper (Deolalikar, Vinay; Hamkins, Joel David; Welch, Ralph (October 2005). "P ≠ NP ∩ co-NP for Infinite Time Turing Machines". Journal of Logic and Computation (Oxford University Press) 15 (5): 577-592. doi:10.1093/logcom/exi022. ISSN 0955-792X. Retrieved August 9, 2010. ), rather than the manuscript currently circulating. Jodi.a.schneider (talk) 10:58, 9 August 2010 (UTC)[reply]
Here's a link that might be useful for that: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm --Waldir talk 13:00, 9 August 2010 (UTC)[reply]
That link is already in the article. Deolalikar's result about infinite time Turing machines (pdf) is interesting but has not much to do with the version of the problem that anyone cares about.
  • I very strongly disagree with the fact that there is no mention of this claimed proof in this article. It would only have to be a few sentences that mention that Vinay Deolalikar has claimed to have proven this result and (regularly updated) information on the status of the peer review. Not only is Deolalikar a respected researcher who has proven original results in complexity theory before, but several other leading researchers have described the proof as 'a serious attempt'. Specifically, I think that based on the reception that this news has already received within the computer science community, and the obvious interest in this question on the wikipedia page (including lots of people adding this information and getting reverted) this article needs to at least mention this claimed proof as a current event. Rfrohardt (talk) 13:55, 9 August 2010 (UTC)[reply]
    • I'd just like to point out that Vinay Deolalikar has yet to release a final version of his paper. Also, as a computer scientist myself, I would prefer that the paper is battle hardened over time before appearing in an encyclopedia. fintler (talk) 00:14, 10 August 2010 (UTC)[reply]
  • There are have been tons of failed solutions in the past; here is a list (also mentioned by Waldir above). The one we're discussing is by someone more knowledgable than most, but it's had hardly any review yet. I'm not holding my breath. This has happened plenty of times before, for all the big important open problems. 75.62.4.94 (talk) 15:19, 9 August 2010 (UTC)[reply]
    • Nobody is suggesting you hold your breath waiting for confirmation/rejection. If we wanted to include references to other well-known failed attempts I would be in favor of that, and it might actually be a nice addition to the article specifically because it has happened many times, and also because there are several interesting results on how hard it is to resolve P=NP. Obviously saying anything other than "this purported proof is out there and serious people are taking it seriously" would be premature, but considering the buzz this has generated already, I think this is worth addressing in the context of a being a current event/development. I count 9 people trying to add it and getting reverted, and I don't think this is 'vandalism' but people just thinking it is worth adding and not looking at the history or talk page first. Rfrohardt (talk) 15:46, 9 August 2010 (UTC)[reply]
      • Wikipedia is not slashdot, and I'm unimpressed by the "buzz" you mention (a slashdot post full of ignorant comments, and posts from more serious blogs (Lipton, Aaronson) where the response is much more skeptical). I expect this proof to be withdrawn or refuted within one week. If that hasn't happened by then I'd be ok with adding a mention. Kempe's failed proof of the 4-color theorem was published in a journal and believed for many years, so asking for this thing to last a week on the internets doesn't seem to be excessive. 75.62.4.94 (talk) 16:13, 9 August 2010 (UTC)[reply]
        • FWIW, the one member of our department who took the trouble to look at the paper more closely than just skimming through the abstract (though he did not actually read it) concluded that it is almost certainly bogus. The impression he got from the paper is that there are plenty of definitions, fancy colour pictures, and long-winded prose, but actual mathematical content seems nowhere to be found. One would expect a fair share of calculations and formulas to start showing up at some point (especially since he is relying on very quantitative results like some of Achlioptas' stuff on k-SAT threshold, and combining these with structural results in descriptive complexity), but they are conspicuously missing in the paper. I'm thus deeply skeptical.—Emil J. 16:30, 9 August 2010 (UTC)[reply]
    • I think that you make good points and that my excitement as a theoretical computer science student has biased me, nonetheless, I think that claims like "One would expect a fair share of calculations and formulas ... but they are conspicuously missing in the paper" and "I expect this proof to be withdrawn or refuted within one week" are as premature as excitement over the result. I especially don't buy the Bayesian inference argument to doubt this proof. Waiting longer to mention the result on Wikipedia is reasonable, but I don't think that the standard for inclusion needs to be 'conclusively confirmed by experts' but rather 1) significant coverage in the mainstream media and/or 2) consensus among experts that the proof seems reasonably likely to be correct. 138.15.100.103 (talk) 18:04, 9 August 2010 (UTC)[reply]
      • I haven't asked for conclusive confirmation by experts, but the current situation is that AFAIK, not a single expert has said even informally that they think the proof looks right. 75.62.4.94 (talk) 20:08, 9 August 2010 (UTC)[reply]
  • For what it's worth, if we're going to include notable proofs we should probably include the proofs of P=NP by Ted Swart in terms of linear programming in 1986/1987, which were notable enough for them to formally refuted in a general setting by Mihalis Yannakakis. It's the first one mentioned at [1]. Swart's original proof contained a very subtle flaw (see [2]), and I certainly wouldn't rule out that such a subtle flaw exists in this proof as well, although I don't have a sufficient background in statistics to evaluate it myself without a lot of work. Dcoetzee 02:04, 10 August 2010 (UTC)[reply]
  • If I claim to have proven the conjecture, would you be in favor of including me in the article? Additionally, I am not claiming the author is a crackpot, but may I remind everyone that going public before the results have been peer-reviewed is the first and best indicator of crackpot research. X —Preceding unsigned comment added by 131.130.16.86 (talk) 15:44, 10 August 2010 (UTC)[reply]
    • He did not “go public before the results have been peer-reviewed”. He emailed his proof to other mathematicians asking for comments, and one of them leaked it to someone who put it on their blog. It wouldn't have taken you more than a few minutes to learn this (e.g. by reading the entire discussion here), if you'd bothered. DES (talk) 18:51, 12 August 2010 (UTC)[reply]
  • I am torn here. Certainly, there is no rush to "cover" this: after all, Wikipedia is an encyclopaedia, not a news site. On the other hand, the claim has been taken seriously enough so that a link to an expert evaluation (as opposed to a "post full of ignorant comments") can be provided. The best source, at the moment, seems to be the polymath wiki Deolalikar's P!=NP paper, which aims to centralize the discussion and links to other resources. I think that it's well worth adding it to the references or external links. As a positive side effect, that would relieve the pressure to update the article before things clear up. Arcfrk (talk) 16:30, 10 August 2010 (UTC)[reply]
  • Not being a mathematician or a computer scientist myself, I am curious why all those in the field are always so quick to label someone with a possible proof a "crank" or "crackpot". Is it so improbable to think that at some point in history a proof will come into existence? —Preceding unsigned comment added by Xcelerate (talk • contribs) 20:34, 10 August 2010 (UTC)[reply]
    • Short answer is yes, it's improbable. Even in the cases where the proof was correct the person behind wasn't exactly normal, like Wiles with his insane obsession and secrecy, or like Perelman who posted the proof somewhere on arXiv and didn't care for a whole three years (!!!) and then rejected the 1mil prize (!!!). Except for this, 95% of the papers claiming to have such proofs are written by clear crackpots (RH suffers the most from it). Another 4.9% suffer from a small oversight which almost always destroys the proof. Only 0.1% of these "groundbreaking" papers are correct (they still have errors, but they're minor). Besides, 40 years is not so much for a such hard problem in a such new field. This paper however, has a lot of potential even if the proof itself is bogus, because it does present a few interesting ideas. Max (talk) —Preceding undated comment added 21:18, 10 August 2010 (UTC).[reply]

Potential solution: break

  • Not mentioning the proof by a single word in the article is just downright stupid. The mention does not have to credit or discredit the proof. There are a bunch of wrong proofs given for a number of problems over time and they have mention about the most famous attempts in their articles. As the normal visitor amounts to this article has become eightfold lately the public clearly is interested in this article exactly because of the circulating proposed proof and thus a good mention of the still very speculative nature of the proof should be incldued http://stats.grok.se/en/201007/P_versus_NP_problem . Gillis (talk) 14:25, 11 August 2010 (UTC)[reply]
    I tend to agree. This attempt has certainly received significant coverage in multiple reliable sources and hence is notable. That is the necessary requirement for inclusion. I have tentatively added a section on notable attempts to the article. — Martin (MSGJ · talk) 17:02, 11 August 2010 (UTC)[reply]
    Wikipedia is not a newspaper. I fail to see the incentive to put the mention of the manuscript here until the dust settles. Once peer reviews will come in a clear picture will form, and this manuscript will find its way here if it's justified. You can rest assured about that. IIRC Perelman's proof was on arXiv for three years and no one cared one bit (except for the people involved), what's the rush now? Max (talk) —Preceding undated comment added 19:17, 11 August 2010 (UTC).[reply]
    Because regardless of whether or not the proof is successful, the attempt is undeniably notable and thus qualifies for inclusion. No, we are not a newspaper but we are not a conventional encyclopedia either and we can be up-to-date. Our readers expect an up-to-date encyclopedia article and I suggest that this attempt should form part of that. — Martin (MSGJ · talk) 08:15, 12 August 2010 (UTC)[reply]
    I agree that the manuscript has gained much public attention, furthermore, I think that this manuscript will have an actual impact on the field even if it's fatally flawed. However, why not open an article on Wikipedia which will list all important manuscripts regarding P=?NP ? Deolalikar's manuscript can be included there, along with other important papers, like Yanakakis's paper and Swart's papers. As the matter stands, whether the paper is correct is still in the speculation phase, while Wikipedia should strive to publish only well known facts or widely accepted views on a scientific article. Max (talk) 13:50, 12 August 2010 (UTC)[reply]
    Yes, and I would encourage you to add other notable papers to P versus NP problem#Notable attempts at proof (I think a separate article would only be appropriate if that section got too long). We are only publishing well known and verifiable facts, i.e. that this attempt has been made and its correctness is yet to be verified. Just because not everything is known about a topic is not a reason to exclude what is known. — Martin (MSGJ · talk) 14:08, 12 August 2010 (UTC)[reply]

P must be equal to NP due to ontology

I need to complain that two particularly important concepts are not given due representation in the P versus N problem article.

1., If P not equal NP, then God cannot exist.

(P=!NP would allow easily creating a problem which God himself cannot solve, making omnipotence impossible. Science is not allowed to prove/disprove the exitance of God per definition, thus P must be equal to NP, where even a non-constructive proof would allow for a God.)

2., If P != NP, that means information can be effectively destroyed by encrypting it, killing the encrypter and spending more time than the available lifetime of the Universe to try regain the info from the encrypted archive.

However, we know from black hole physics that information cannot be destroyed. If things fall into the event horizon, their info content is radiated away via a not fully random electron-positron pair generation outside the event horizon. See the works of Prof. Stephen Hawking. If information could be destroyed, beings could destroy the Universe by depriving it of information, so its material would lose structure. This does not happen, therefore information cannot be destroyed, therefore P=NP is necessary. 84.21.2.137 (talk) 09:41, 9 August 2010 (UTC)[reply]

I don't believe in your god (or any other), but claiming that P =/= NP somehow proves or disproves the existence of a supernatural being is just silly. NP problems are not unsolvable, they just take a very long time to solve by conventional means. It may or may not be possible to solve them very quickly using quantum computers, and wouldn't an all-knowing god, well, just know the answer? As for your second claim, it is based on several incorrect premises: firstly, neither encryption nor decryption are NP-complete, although key recovery can be, depending on the algorithm; secondly, encryption does not destroy information, it just transforms it; and finally, information can be destroyed. In fact, the second law of thermodynamics says that information is being destroyed all the time, and suggests that we are headed toward a future (albeit a very distant future) in which no information exists at all. DES (talk) 10:02, 9 August 2010 (UTC)[reply]
>encryption does not destroy information, it just transforms it
Really strong encryption takes meaningful input and produces a garbage-looking output stream that simply cannot be distinguished from pure noise without having the decipher key at hand. If the cipher key is lost/destroyed, the crypto is truly strong and P does not equal NP, then there is no possibility to prove (before the Universe burns out) that an allegedly "crypto" data stream contains hidden information rather than pure noise. This means information was destroyed, because no-one can prove that it still exists! However, if P=NP, then you can guaranteed retrieve the plaintext info or determine that it is indeed just noise, and with a bounded amount of effort, hopefully in a time less than the remaining lifespan of the Universe. 91.82.168.184 (talk) 21:13, 10 August 2010 (UTC)[reply]
Plus, your description of Hawking radiation is not accurate. Information is not retained via Hawking radiation. Rather, the information is retained on the surface of the event horizon (shown by Susskind). As for the first reply, entropy is not the destruction of information. Information /can/ neither be created nor destroyed, per the laws of thermodynamics. Anyway, if there were a mathematical theorem that were to prove the non-existence of God, I would think it would be Godel's Incompleteness Theorem. Prothonotar (talk) 19:06, 9 August 2010 (UTC)[reply]
Hmm, I don't see anything about conservation of information in the laws of thermodynamics, but I'm a CS guy, not a theoretical physics guy, so my understanding of this may be tainted by our use of the term “entropy” in a different sense. However, say you encode information by alternately heating and cooling one-inch sections of a steel wire. Let's ignore dissipation to the environment; over time, the heat will spread evenly throughout the wire, per the zeroth law of thermodynamics, and the information will be lost. Assuming you are correct, where is the flaw in my example? DES (talk) 22:45, 9 August 2010 (UTC)[reply]

Solved?

Looks like Vinay Deolalikar (here is his page at the hp webstite) has solved the issue... He came to the conclusion that P is not equal to NP

Preliminary details here.

(posting for some people of goodwill to update the article...)

Paolo (not registered yet, sorry) —Preceding unsigned comment added by 151.99.187.181 (talk) 15:10, 9 August 2010 (UTC)[reply]

Please see the "potential solution" section further up. Based on current discussion at RJ Lipton's blog, the "proof" appears to have some gaps right now. 75.62.4.94 (talk) 15:25, 9 August 2010 (UTC)[reply]
Does that make his attempt non-notable? Why not mention it?--88.74.222.13 (talk) 17:22, 9 August 2010 (UTC)[reply]
Notability is established by documentation in reliable sources. Topics are presumed non-notable until documented as notable, not the other way around. Right now there are (as far as I can tell) zero recognized experts saying (even informally) that they think the proof is correct. If any of them do, I'd reconsider. 75.62.4.94 (talk) 17:40, 9 August 2010 (UTC)[reply]
This proof has been quite pushed by some blogs ([3]) and the press seems to take notice too (for example [4]) According to [5], 'Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.”' --rtc (talk) 18:36, 9 August 2010 (UTC)[reply]
"Serious attempt" just means it's not by some crank, not that it's a correct proof. Neither Cook, Lipton, nor anyone else in the field has (AFAIK) said they think the proof is correct. If someone does (as happened with Perelman), then it gets more interesting. Right now this situation is a yawner. 75.62.4.94 (talk) 18:41, 9 August 2010 (UTC)[reply]
It's not a criterion that it has to be correct. Notability is enough, and this solution attempt has become notable. --rtc (talk) 20:51, 9 August 2010 (UTC)[reply]
I'd say noncommital blog posts and a random popular press mention don't establish notability for a purported theoretical result like this. A write-up in a CS journal would be more promising, or favorable posts from the research bloggers (the latter are not supposed to count either, but I'm not that big a policy zealot, I just want to do what makes sense, and the current situation does not qualify). I'd even be satisfied (as mentioned earlier) if the claim holds up for 1 week without being refuted. We could take it out if it were refuted later. 75.62.4.94 (talk) 21:16, 9 August 2010 (UTC)[reply]
Why? Regardless of whether it's a valid or an invalid proof, it has already had some impact. It's notable. And even if the validity is challenged next week, it is still notable. Wikipedia is not supposed to describe only valid proofs and true ideas. All the experts who had a look at the paper acknowledged that it contains new ideas that have merit even if the overall proof should turn out to be invalid. --rtc (talk) 21:50, 9 August 2010 (UTC)[reply]
Well, Scott Aaronson said something like that; nobody else did as far as I've noticed. Of course every published research paper should contain a new idea that has merit, otherwise why publish it? New idea != notability. Something like Tao's remarks about Perelman's Poincaré conjecture paper p.2 top would carry more weight, but only after the paper had been circulating for a while, much longer than 1 day. In short, this thing is way premature. Wikipedia is not a crystal ball or a newspaper. 75.62.4.94 (talk) 22:51, 9 August 2010 (UTC)[reply]
As I mentioned above, I think this proof is roughly comparable in terms of its seriousness and the reputability of its author to the proof of P=NP by Ted Swart in the 1980s. If it's mentioned, both should be mentioned as "notable proof attempts" - otherwise both should be omitted. Whether we document notable proof attempts is an editorial decision. Dcoetzee 02:11, 10 August 2010 (UTC)[reply]
I'm somewhat familiar with the Ted Swart saga and I agree that the comparison is reasonable. I don't think either attempt should be mentioned explicitly in the article. I'd prefer to just mention Gerhard Woeginger's page (currently in the extlink section) as a list of proposed solutions of varying quality that have not gained general acceptance from the research community. There is a citation along those lines in the RH article and we can do something similar. 75.62.4.94 (talk) 06:52, 10 August 2010 (UTC)[reply]
FWIW Richard Lipton wrote a good blog post a while back [6] that among other things described a failed attempt by Edward Nelson in the 1990's to prove P!=NP. 75.62.4.94 (talk) 08:05, 10 August 2010 (UTC)[reply]
I would tentatively support a "notable proof attempts" section. I think that there is enough information on previous attempts, and that this should be useful perspective for our readers. But I would advocate delaying as long as reasonably possible on the Deolalikar proof attempt: we just don't know that much about it yet. CRGreathouse (t | c) 12:48, 10 August 2010 (UTC)[reply]
I don't think there have been any really notable attempts in the past. This current one has gotten more attention than earlier ones because of the internet buzz machine that didn't exist in the 1990's etc. The current one seems to have been withdrawn from the author's web site, but if it returns I'm coming around to the idea that we should mention it, because of the amount of attention it's getting. I still support deleting the biographical article about the author or redirecting it to here. I don't think it's doing the person any good and in absence of info to the contrary I'm going to treat it as an involuntary biography (one that the subject would opt out of if he could). 75.62.4.94 (talk) 18:54, 10 August 2010 (UTC)[reply]
Interesting. I *do* think there have been notable attempts, though I'm not sure that this recent one is an example of one. CRGreathouse (t | c) 23:43, 10 August 2010 (UTC)[reply]
Let's compare the situation with Alfred Kempe's erroneous proof of the 4-color theorem that was accepted as correct for decades. That was really very famous and actually significant, and it was around 100 years ago so there's been plenty of time for historical documentation to develop. Yet we only have about 2 sentences about it, and that really seems like enough. 75.62.4.94 (talk) 03:05, 11 August 2010 (UTC)[reply]

biography

Someone has written a biography Vinay Deolalikar, sigh. I have suggested on its talk page that it be afd'd. 75.62.4.94 (talk) 16:20, 9 August 2010 (UTC)[reply]

AfD is now in progress. 75.62.4.94 (talk) 17:40, 9 August 2010 (UTC)[reply]

What?

Um, what is this? Articles usually start off with "The P versus NP Problem is..." followed by a description that it not too technical for the average reader... Sephiroth storm (talk) 00:38, 10 August 2010 (UTC)[reply]

Good point, the intro really does need work. I rewrote the first sentence but will have to do some other things soon. 75.62.4.94 (talk) 01:01, 10 August 2010 (UTC)[reply]
I added a less formal definition of P and NP closer to the lead. Unfortunately, this means that we return to defining the same terms three times in the same article, in increasing detail, but at least it should be possible to skim the lead section for a basic understanding now. — Gavia immer (talk) 01:51, 10 August 2010 (UTC)[reply]
Some more tightening is possible but in any case it's more readable now than it was before. The whole article could actually use cleanup and polishing. It's quite an important article but currently a bit haphazard. 75.62.4.94 (talk) 06:57, 10 August 2010 (UTC)[reply]

I've rewritten the intro, putting more emphasis on the real world impact of this unresolved question, so that it's importance is easier to grasp by people who neither know maths, nor care about maths. IMO, this article should be able the 'problem', its implications, and ongoing progress on the solution, and leave the difficult 'explain the maths' to be covered in more detail in the articles about complexity theory. John Vandenberg (chat) 05:05, 13 August 2010 (UTC)[reply]

Why restrict to computer solutions?

I've been copyediting some of the text. Not sure what to do with this sentence, Informally, it asks whether every problem with a yes-or-no answer whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.. Is it important to the core of the P v NP problem that a computer be involved? Would it be correct to rewrite the sentence as, Informally, it asks whether every problem with a yes-or-no answer whose solution can be efficiently checked can also be efficiently solved? -- RoySmith (talk) 16:13, 10 August 2010 (UTC)[reply]

The formal definition of the relevant complexity classes involves the number of steps a Turing machine (a theoretical model of a computer) would require to resolve a problem, so for formal consideration it is important. Even for the lead, where we should have an informal introduction, I think that mentioning the involvement of a computer (or other algorithm model) is useful to make it clear what's being reasoned about here - to avoid having readers come up with the false "insight" that they can simplify things by, e.g., "just knowing" the result of some basic math. That, in turn, is useful to the discussion of why relativizing proofs can't work. Please do continue banging on the lead to get it into shape, but I think we can't avoid introducing "on a computer" there. It is at least simpler than having a lengthy digression into formal models of computation at the top of the article. — Gavia immer (talk) 16:29, 10 August 2010 (UTC)[reply]
Unless one says something about the methods which can be used to solve the problem, then someone could say "... and then one asks an oracle (or God) for the answer and verifies it.". JRSpriggs (talk) 17:08, 10 August 2010 (UTC)[reply]
I think most of the recent edits to the lead have been ok, but the current version[7] has been oversimplified a little bit too much. I'm also thinking of trying to write a nontechnical overview, changing the subset-sum example to primality testing (as a problem once thought intractable but later shown otherwise) and travelling salesman (the archetypal NP-hard problem), before talking about nondeterministic machines and suchlike. The idea is that it's sometimes possible (e.g. in primality testing) to get around the apparent need for brute force searches by clever means; the P-vs-NP problem asks whether that's always possible, and is of intense interest for many theoretical and practical reasons. I'd also like to spend a bit of space describing Impagliazzo's "Five worlds" scenarios. While that paper doesn't get all that much attention in the literature, I think its points are generally accepted and so it's ok to use it for expository purposes. Any thoughts? 75.62.4.94 (talk) 18:46, 10 August 2010 (UTC)[reply]

In what way is it oversimplified? I'm not trying to pushback on your comment, just to understand it better. This is a highly technical topic, and there is a tendency for articles about such topics to become impenetrable to non-experts. I think the early part of the article should try to explain what this is all about in a way that an educated lay person could come away with some understanding. If that means over-simplifying, I think that's OK. There's plenty of space left in the rest of the article to dig into the details with greater rigor.

I see several key concepts here. One (hinted at by the explanation of "quick") is the idea of algorithmic complexity. The very concept of "a problem being hard to solve" is interpreted differently by computer scientists and lay people. You might think that conducting a census of the US population is a hard problem, but a computer scientist would shrug it off as, "Feh, that's O(n). Easy". So, we need to impart some flavor of that.

Next, the concept that there are "classes of problems" is likely to be an alien concept. The idea that counting the number of fish in your aquarium and adding up the change in your pocket are somehow "just as hard" as each other takes some explaining. Or that sorting a bridge hand is "harder" than counting how many cards remain in an 8-deck card shoe.

Next, you have to explain the idea that verifying that an answer is correct is a different problem from coming up with the answer in the first place. And, then, why anybody cares to compare the relative difficulties of these.

Add to that the unfamiliar terminology used in the field, and figure out a way to explain all that so that somebody who doesn't have a degree in higher math. And do it in a short enough hunk of prose that they don't zone off before they reach the end of the second paragraph. If you can find a way to do that without "oversimplifying", my hat's off to you. -- RoySmith (talk) 19:22, 10 August 2010 (UTC)[reply]

I don't think the article can go any farther than it does without providing an example, because there's no way to really understand what a certificate is without an example of a certificate. I also think that the first example in the article had better be one of the simple arithmetic problems (subset sum or knapsack, and subset sum is slightly easier to parse), because that's all the math we can afford to assume a reader has. If we use an example like SAT or the graph problems, they will fail to understand it and the "understand what you're reading" switch in their brain will permanently turn to "no", preventing them from understanding the rest of the article. I think that even the traveling salesman problem is too complicated for the first example, if we can avoid using it. — Gavia immer (talk) 22:56, 10 August 2010 (UTC)[reply]
In the nontechnical overview we'd describe TSP in everyday terms of a salesman visiting cities. No graphs. Everybody understands this. That's why it's an archetype after all. 75.62.4.94 (talk) 01:03, 11 August 2010 (UTC)[reply]
I think the intro has become a bit oversimplified since it has to clearly state P vs NP is about computational problems, not "is there any person in the world who can juggle bowling balls with their feet" (a yes-or-no question whose answer can easily be verified by exhibiting such a person, but otherwise not solved except by brute force search, a situation Baker Gill and Solovay anticipated with their proof about oracle separations). One clearly does not need a mathematics degree to understand the problem (including a technical level with the relevant terminology), since it is taught in undergraduate CS classes, by definition to people with no degrees. I think we are ok if the non-technical intro assumes reasonable scientific literacy, then we have a more technical description at the undergraduate CS level, then some hand-wavy discussion of the current state of research knowledge, with appropriate citations to the actual references and wikilinks to more technical articles. I'd like to restore the wording describing P/NP as a problem in TCS and logic. CS is a wide area including topics like programming language design. Even TCS is rather wide, since it includes things like computability theory, algorithm construction (of algorithms for particular problems), etc. Complexity theory (the part concerned about proving lower bounds and dealing with concrete complexity classes) is an area within TCS that is really rather specialized, but that is where the P vs NP problem comes from. 75.62.4.94 (talk) 23:59, 10 August 2010 (UTC)[reply]
Compare the following two first sentences (roughly, the one that's there now, and the one that used to be there):
The P versus NP problem is a major unsolved problem in computer science.
The P versus NP problem is a major unsolved problem in theoretical computer science and mathematical logic.
Is the second one more accurate? Probably. But, the first one is certainly not wrong. Now, put yourself into the shoes of somebody who just heard about this on slashdot or maybe the science column in the newspaper, or maybe some people talking about it at lunch. Your math background is whatever you remember from high school or perhaps college. You probably did some proofs in geometry class, a long time ago. Maybe you can even still work some differential calculus problems. Maybe you're even pretty good at hacking out some Perl code. You came here to figure just what the heck this P != NP stuff is all about. Will the second sentence help you get your head around it any better? I don't think so. -- RoySmith (talk) 00:25, 11 August 2010 (UTC)[reply]
I like the second sentence better. The version in the article used wikilinks that explain the named subject areas if you click on them. I also think the second sentence also sets an appropriate tone for the article. It is perfectly accessible for someone who reads slashdot or a science column. 75.62.4.94 (talk) 01:00, 11 August 2010 (UTC)[reply]

Please improve the layman section

Why is the following problem not a member of P? Find the Man in the Yellow Hat: Curious George likes to lie. He will say someone is not the man in the yellow hat when he is, but he won't say he is the man in the yellow hat if he isn't. The first time you ask George he has a 100% chance of admitting it is the man in the Yellow Hat if it is. Each time after his odds of getting him to admit it, drops by 50%. BTW. I think I understand why it is not part of P, but it is not clear from the layman section. 24.36.199.169 (talk) 13:38, 11 August 2010 (UTC)[reply]

Mentioning decision problems in the lead

I just undid an edit by 91.193.157.170, which (effectively) changed all mentions of "decision problems" to just "problems", "certificates" with "solutions", etc. — a more informal statement of the question. I believe stating it precisely is important to avoid confusing readers, but if someone thinks that just talking of "problems" is simpler and "good enough", feel free to re-do. Shreevatsa (talk) 03:12, 13 August 2010 (UTC)[reply]

It is a matter of decision problems, and not general function problems, and we ought to state that plainly, so I think your revert was correct. Moreover, we do mention the function problem version at the end of the lead. Of course, in either case it's the underlying algorithms that get the attention, and not the particular form of the result. We ought to feel free to handwave the decision step anywhere that it doesn't add to the explanation, but we shouldn't simply ignore it. — Gavia immer (talk) 03:51, 13 August 2010 (UTC)[reply]
I agree with your revert, and would prefer 'decision problem' to be visible in the intro without being hidden under 'problem with a yes-or-no answer' as I attempted in my revision (which you reverted) John Vandenberg (chat) 05:21, 13 August 2010 (UTC)[reply]
Oh sorry, I didn't notice I was reverting your edit. But looking it at now I think you should discuss your edit separately; e-commerce and cryptography don't generally rely on the hardness of NP-complete problems but that of problems like factoring and discrete log which are believed not to be NP-complete. Shreevatsa (talk) 05:51, 13 August 2010 (UTC)[reply]
No worries; I was nearly going to put it here on the talk for discussion anyway.
wrt to PKC, arn't these cryptographic algorithms still in NP (ignoring which subclass they reside in)? i.e. the verification algorithms need to be feasible in order to be usable for PKC in the real world. We list PKC in the section P versus NP problem#Consequences of proof, and factoring in NP (complexity)#Examples. John Vandenberg (chat) 10:16, 13 August 2010 (UTC)[reply]
The normal use of cryptographic algorithms is in P. Cryptanalysis (attempts to break the cipher and get the key or plain text by an unauthorized person) is intended to be difficult, and is in NP. But for practical crypto-systems, cryptanalysis is not known to be NP-complete at this time.
However, the danger to cryptography of finding that P=NP is far overshadowed by the immense benefits that would be enjoyed by other computational applications. JRSpriggs (talk) 11:55, 13 August 2010 (UTC)[reply]
The edit had nothing to do with "decision problems" vs "problems", etc.
The introduction currently refers to problems *with a yes/no answer*. However, it does not become clear why only this kind of problems is relevant. In fact, if you can easily check the answer of a yes/no problem, then you can easily compute it - just check the 'yes' answer, then the 'no' answer.
When I originally fixed this, I included a reference to the Clay Mathematics Institute page on the problem, which supports my version of the introduction, but which nobody seems to have bothered to check. See here: http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof for a reason why that institute's definition of the problem can be trusted.
Since the article in its current state does not make sense (possibly unless one is familiar with some very specific and counter-intuitive terminology, in which case one wouldn't need this article), I am redoing the edit. Before undoing it again, please give a valid and logical reason why my argument is wrong. 91.193.157.170
And indeed you have. It's a good idea to discuss first before re-doing a change (the bold-revert-discuss cycle), as not doing so can lead to edit wars. Anyway, to (re-)start the discussion: you are right that it's not the answers ("Yes" or "No") that can be easily checked, but certificates, which are "proofs" for the yes case. It is part of the definition of P and NP that they only refer to problems "with a yes/no answer" (but as the paragraph you removed says, FP v/s FNP is equivalent to P vs NP). I'll leave it for others to discuss, but hopefully the end result will be something that clear to all. Shreevatsa (talk) 22:15, 13 August 2010 (UTC)[reply]
"It's a good idea..." - I completely agree with you on this. In this specific case I breached the rules because everybody seemed to have misunderstood the point of the edit.
I also agree with your other points. However, the article in its previous state was confusing for people lacking your mathematical background, as I believe I showed in the 2nd previous post. Please note that due to the recent attempt at a solution, this problem has become popular, and we cannot expect everybody who searches for it to know as much as you.
I promise not to edit this page any more, my intentions were far from starting an edit war. 91.193.157.170

Proof of a computation versus proof of computability

At the end of section P versus NP problem#Polynomial-time algorithms, it says "However, this is only guaranteed to work if there is a provable polynomial time algorithm for SUBSET-SUM; one might imagine an algorithm which works but cannot be proved to work.". Assuming subset sum is in P, it is possible that there might not be a proof (in ZFC, say) of that fact. However, for any specific computation in polynomial time that finds a subset (which adds to zero) of a specific set, there will be a proof of that fact and that proof can be done in polynomial time. It is this latter proof which is at issue here. JRSpriggs (talk) 19:32, 13 August 2010 (UTC)[reply]

Yeah, that's why I had removed it. The section could be written more clearly, but the algorithm would be polynomial-time as long as P=NP is true as a fact, whether we can prove it or not. Shreevatsa (talk) 22:22, 13 August 2010 (UTC)[reply]
Actually, the whole part (starting at "Perhaps") is confusingly written. It just says, in convoluted terms, that P is closed under complement. (Thus if P=NP, then P=NP=coNP=NP∪coNP=NP∩coNP, so SUBSET-SUM can be decided in polynomial time.) And this is just stated, not (effectively) explained. How about trimming it? Shreevatsa (talk) 00:47, 14 August 2010 (UTC)[reply]
Yes, I looked at it again and realized that it is (in part) claiming that if the answer is "no" and P=NP, then one can prove that the answer is "no" in polynomial time. That may not be possible because there is no polynomial which is an upper bound for all polynomials, so I deleted the second algorithm. JRSpriggs (talk) 02:00, 14 August 2010 (UTC)[reply]
No, the claim is correct. As I said, if P=NP, SUBSET-SUM is also in co-NP, so a proof that there is no subset adding up to 0 exists and can be found in polynomial time. The algorithm actually works (there is a polynomial bound on a proof of either Yes or No), but the explanation was unclear. Shreevatsa (talk) 02:11, 14 August 2010 (UTC)[reply]
Sorry. JRSpriggs (talk) 16:32, 14 August 2010 (UTC)[reply]
This is wrong. Of course, for any input S of a polynomial-time algorithm there is a polynomial-time constructible proof that the algorithm gives such-and-such output on S. However, there is no way to conclude from this that we have a polynomial-size proof that S is not in SUBSET-SUM, unless we can prove that the algorithm is correct.—Emil J. 12:53, 16 August 2010 (UTC)[reply]
That is, you are right that the needed assumption is slightly weaker than having a provably correct P-algorithm for an NP-complete problem: your argument works assuming that (1) there exists a coNP-algorithm which provably solves an NP-complete problem (which implies that both positive and negative instances of SUBSET-SUM will have poly-size proofs) and (2) P = NP (which implies that these proofs can be find in polynomial time). However, I don't see this to make much of a difference, and in any case you still need to assume the provability of something.—Emil J. 13:54, 16 August 2010 (UTC)[reply]
No, you don't need. Suppose P=NP. Then because P is closed under complement, coNP=NP=P as well. So (because SUBSET-SUM is in P), you have a polynomial-time algorithm (say steps for input of length n) accepting SUBSET-SUM, and (because (SUBSET-SUM)∁ is in NP) you have a polynomial-time algorithm (say steps) accepting SUBSET-SUM∁. Just run these two in parallel, and you have a polynomial-time algorithm (in steps) deciding SUBSET-SUM. (You don't have to actually run the two in parallel because the algorithm is the same, but whatever.) Nowhere do you need to assume the provability of something. (Of course, to prove an actual bound on the running time of the algorithm, you need an actual bound on the running time of SUBSET-SUM -- but you don't need any provability to say that "If P=NP, this algorithm is polynomial-time as well".) Shreevatsa (talk) 17:12, 16 August 2010 (UTC)[reply]
Sigh. Recall that we are discussing this algorithm:
FOR N = 1...infinity
FOR P = 1...N
Run program number P for N steps with input S
IF the program outputs a complete math proof
AND each step of the proof is legal
AND the conclusion is that S does (or does not) have a subset summing to 0
THEN
OUTPUT "yes" (or "no") and HALT
It obviously solves SUBSET-SUM, and you claim that assuming just P = NP, this algorithm runs in polynomial time. In order for this to be the case, you have to establish (among others) that for any input S ∉ SUBSET-SUM, there exists a "complete math proof" (let's make this precise by asking for a proof in ZFC) of the statement
(*) no subset of S sums to 0
of size polynomial in the length of S. Where did you show that? I see a lot of talk about algorithms in your post, but you did not show the existence of any proofs.
Now, here is where I suspect your confusion is. If P = NP, then there is an algorithm, lets call it A, which solves SUBSET-SUM in polynomial time. Then, given S as above, we can find in polynomial time a polynomial-size ZFC proof of the statement
(**) algorithm A rejects input S.
That's all very nice, but (**) is not (*). The only way I can see to construct a ZFC proof of (*) from a proof of (**) is to use a ZFC proof of the statement
(***) A does not reject any positive instances of SUBSET-SUM,
i.e., (half of) the statement of correctness of A. If there is another way, show it.—Emil J. 17:57, 16 August 2010 (UTC)[reply]
(edit conflict) Oh, that algorithm is pretty poorly written, and it's not worth discussing it in too much detail. As I've been saying, the conclusions were correct, but the section was unclearly written. So let's rewrite it properly, without talking of "complete math proofs" unless necessary, since they can lead to confusion like the questions you raise. (In fact, the algorithm is actually correct: in either case there is a certificate of polynomial length, which can be verified in polynomial time, so there is always a polynomial-length "proof", which can be quite easily converted to a formal proof in ZFC. For instance, for the case of YES instances, the proof would involve what the earlier algorithm says: "the program outputs a list of distinct integers AND the integers are all in S AND the integers sum to 0", then you can mechanically convert that into a proof. For the case of NO instances, it's not immediately obvious what such a proof would look like, since we don't know or believe SUBSET-SUM is in coNP, but if P=NP, then there is always such a proof. But it's better to avoid mention of proofs and ZFC altogether if possible, because that sort of detail is not germane to the point here.) Shreevatsa (talk) 18:31, 16 August 2010 (UTC)[reply]
You keep asserting the existence of proofs without justification, and as far as I can see, you are wrong in both places where you do so. You need to prove in ZFC the correctness of the algorithm in order to convert a certificate for the NO instances into a ZFC-proof. You don't need it for the YES instances because summing to 0 is ZFC-provably polynomial-time decidable. The algorithm is correct, but not necessarily polynomial-time.
Because SUBSET-SUM is in NP, there is a polynomial-time certificate for the YES instances — which, along with its verification, is a proof. If SUBSET-SUM is in coNP (which we assume when we assume P=NP), there is a polynomial-time certificate for the NO instances — which, along with its verification, is a proof. Shreevatsa (talk) 19:04, 16 August 2010 (UTC)[reply]
It is a proof of "this-and-this algorithm accepts S". It is not a proof of "S is not in SUBSET-SUM".—Emil J. 10:40, 17 August 2010 (UTC)[reply]
PS, after seeing your second edit. No, we don't currently know a way of giving a proof of (*) — obviously, since we don't believe that that SUBSET-SUM is in co-NP. But if P=NP, then if we can "accept" SUBSET-SUM we can "decide" SUBSET-SUM as well, because P=coP. That's all I've been saying! (But let me ask: why do you say (**) is not (*)? If A is correct—and it is, because we already have proved that A is correct if P=NP—then (*) is equivalent to (**).) Shreevatsa (talk) 18:31, 16 August 2010 (UTC)[reply]
Huh? (**) is a different string of symbols than (*). The algorithm above cannot check whether something is equivalent in the real world, it can only check that the proof is formally correct as written. By your argument every true statement would be trivially provable, on account of being equivalent to 0 = 0. We didn't prove anything about A, we assumed that it solves SUBSET-SUM.
We are discussing the running time of the algorithm above, because that's what was incorrectly stated in the article. We are not discussing that P = NP implies P = coNP, which you keep bringing up for reasons which escape me. But regarding the sentence you wrote above: if P = NP, then we can decide SUBSET-SUM, period, we don't need to further "assume" that we can accept SUBSET-SUM.—Emil J. 18:50, 16 August 2010 (UTC)[reply]
If you prove A is correct, and you prove A rejects an instance, doesn't it prove (*) for that instance? (1) We have (or rather Levin has) already proved that A is correct if P=NP. (A being the algorithm currently mentioned in the article.) (2) You accept that we can prove that A rejects an instance. So from (1) and (2), isn't this a proof of (*)? Anyway, you agree that "if P = NP, then we can decide SUBSET-SUM, period". Which was the point of this whole discussion. So let's keep it in the article (which I see was done a few hours ago). So all is good. Shreevatsa (talk) 19:04, 16 August 2010 (UTC)[reply]
What you say here does not make any sense to me. Recall that A was a hypothetical algorithm which solves SUBSET-SUM in polynomial-time, which exists by definition assuming P = NP. Nobody proved it correct, it is not even an explicit algorithm. You seem to be talking about something else.—Emil J. 10:40, 17 August 2010 (UTC)[reply]
I mentioned that A for the specific (Levin's) explicit proved-correct algorithm, not a hypothetical algorithm. But this doesn't matter now, since I see I made a mistake (below). Shreevatsa (talk) 19:42, 17 August 2010 (UTC)[reply]

After some thought, I think I see more clearly where the confusion is (and why the algorithm that was removed is actually correct). Consider the following two algorithms for SUBSET-SUM, which I'll call A1 and A2. A1 is the algorithm in the article, whose idea is attributed to Levin: 

   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a list of distinct integers all in S and they sum to 0,
           THEN
               OUTPUT "yes" and HALT

A2 is: 

   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a proof that S ∈ SUBSET-SUM,
           THEN
               OUTPUT "yes" and HALT

Now we all agree that if P=NP, then A1 is correct (accepts precisely SUBSET-SUM) and runs in polynomial-time. What about A2?

  • 1. If there is a program that in polynomial-time can output a subset, then there is another slightly different program that in polynomial-time can output a proof: just output the subset along with some verification that it all adds up to 0. So A2 is correct (accepts precisely SUBSET-SUM) and runs in polynomial time.
  • 2. Nowhere in the definition of A2 did we use any property of SUBSET-SUM other than the fact that it's in NP. It seems that A2 would work if we replaced SUBSET-SUM with any other language L in NP. That is, define an algorithm A3, parametrized by language L, is as follows. A3(L) is:
   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a proof that S ∈ L,
           THEN
               OUTPUT "yes" and HALT

A2 is just A3(SUBSET-SUM). I claim that for any language L in NP, A3(L) is an algorithm that accepts precisely L, and runs in polynomial-time if P=NP. Whatever the structure of L is, or the reason why it's in NP, there is some program that will output a proof using a certificate for whatever predicate puts L in NP. (More formally: L, being in NP, is defined by some polynomial-length predicate :

and the program would output the certificate c along with a verification that holds, which is a proof that .)

  • 3. Now, if P=NP, then (because coNP=NP), is such a language L. So the algorithm is an explicit algorithm that accepts precisely , and runs in polynomial time.
  • 4. Let A4 be the following algorithm: run and in parallel (one step each, say). If the former accepts, OUTPUT "yes" and halt. If the latter accepts, OUTPUT "no" and HALT. I claim that A4 is an explicit algorithm that decides SUBSET-SUM. (Note that we assumed P=NP to prove both correctness and polynomial-time, whereas earlier we were assuming P=NP only to argue polynomial-time. But this doesn't matter.)
  • 5. The algorithm that was previously in the article is equivalent to A4.

If I've made a mistake, I'd like to know about it. Else, I feel it was unnecessary to remove the algorithm that was in the article. Thanks, Shreevatsa (talk) 20:16, 16 August 2010 (UTC)[reply]

First, wherever you say that A1, A2, etc. run in polynomial time, it actually mean that they accept positive inputs in polynomial time, but runs forever for negative inputs; I assume we agree on this point, but just to make the terminology clear.
Yes, agreed.
The error in your argument is that your A3(L) is not well-defined. You cannot explicitly produce an algorithm like this for a given NP-language L, you can only do it for a given NP-algorithm. Thus your notation is meaningless until you specify an explicit NP-algorithm for . You cannot do that using just P = NP, since that does not give you beforehand an explicit poly-time algorithm for SUBSET-SUM, it only says that an algorithm exists. You can realize your error very easily: just avoid all these abbreviations like An, and try to write down your "explicit algorithm" explicitly.
Ah thanks! Finally, I see my mistake. Thank you very much. Sorry. :-) You are right, A3(L) is not explicit unless we know the predicate for L. That is, even though L is defined as "x such that φ(x,c) is true for some c", and there will exist a program outputting a proof of "there exists c such that φ(x,c) is true" given an x, we would not recognise it as a proof of x being in L. So only something like A3(φ) can be explicit, not A3(L). This is what I somehow missed. The non-explicitness in "IF the program outputs a proof that S ∈ L" is in the "IF"! Even though the program is outputting a proof that would be the same as S∈L if we knew about L, it is not a proof of S ∈ L, and we can't recognise it unless we do know it's equivalent. Oops. This is what you've been saying. Thanks. Shreevatsa (talk) 19:42, 17 August 2010 (UTC)[reply]
Great. I'm glad we are finally tuned to the same frequency.—Emil J. 09:53, 18 August 2010 (UTC)[reply]
The second error is that the algorithm that was in the article is not equivalent to A4. You still seem to be incapable of understanding that differently formulated statements are different objects even though they have the same extension in the real world. A proof of the statement "S is not in SUBSET-SUM" is something quite different from a proof of "S is accepted by M" where M is an NP-machine which happens to solve . The best you can do is that you can transform one of the proofs into the other if you have a proof that M is correct.—Emil J. 10:04, 17 August 2010 (UTC)[reply]
Well, it doesn't matter now, but modulo my earlier mistake, they are the same. A4 has two threads in parallel, one which runs programs waiting for a proof of S ∈ L and one which runs programs waiting for a proof of S ∉ L (which now I realise isn't possible, but that's how I had defined A4), but both of these threads are running the same programs. The algorithm that was in the article just has one thread that runs programs waiting for a proof of either S ∈ L or S ∉ L, so they are equivalent. Anyway, thanks for pointing out the error. Shreevatsa (talk) 19:42, 17 August 2010 (UTC)[reply]
Also, let us keep in mind that the correctness of A2, A3(L), etc., assumes the consistency of the formal system whose proofs are referred to in the algorithm (otherwise the algorithm will accept all inputs). This may become a problem if the system is strong enough.—Emil J. 12:45, 17 August 2010 (UTC)[reply]
To Shreevatsa: Please provide a proof (not relying on the things in dispute here) or on-line reference for "if P=NP, then coNP=NP". JRSpriggs (talk) 18:55, 17 August 2010 (UTC)[reply]
This is trivial: P is closed under complementation (that is, a language is in P iff its set-theoretic complement is) so if P=NP then NP would also be closed under complementation because it would be the same class as P. I'm sure there are references out there somewhere that say this explicitly but it seems to me to be the sort of trivial calculation that doesn't need a reference. —David Eppstein (talk) 19:04, 17 August 2010 (UTC)[reply]
To David Eppstein: Forgive the stupid question, but how do you know that P is closed under complementation? JRSpriggs (talk) 19:35, 17 August 2010 (UTC)[reply]
Suppose that A is a polynomial-time algorithm for a decision problem in P. Let algorithm A' be the algorithm that runs algorithm A and then returns the Boolean negation of its answer. Then A' is a polynomial-time algorithm for the complementary problem. —David Eppstein (talk) 19:58, 17 August 2010 (UTC)[reply]
So are all these complexity classes defined to be subclasses of the class of recursive sets? Or recursively enumerable sets? Or what? JRSpriggs (talk) 23:35, 17 August 2010 (UTC)[reply]
They're certainly subclasses of both of those families, whether or not they're explicitly defined that way. Is there a point to these naive questions? —David Eppstein (talk) 00:00, 18 August 2010 (UTC)[reply]
Well, I had thought I knew what these classes were. But after trying to read the argument above, I realized that I am confused. So I am trying to attain clarity.
In particular, what would it mean for subset-sum to be in P? Suppose there is an hypothetical (1st) algorithm that solves subset-sum in polynomial time and always returns either "yes" or "no" when it halts. If it can be proved to have that property, then certainly the (2nd) algorithm using proofs should do the same thing. Right?
Right. The problem was whether the assumption that "it can be proved to have that property" is actually needed.—Emil J. 09:53, 18 August 2010 (UTC)[reply]
However, I am wondering why the (3rd) algorithm which is currently in the section and searches through sub-calculations including sub-calculations of the (1st) algorithm is allowed to loop forever when the answer is "no". That seems contrary to your definition of P which requires that it always halt with either "yes" or "no". JRSpriggs (talk) 00:32, 18 August 2010 (UTC)[reply]
There is no difference in algorithmic power between, on the one hand, deterministic polynomial time algorithms that always halt with a yes or no answer and, on the other hand, deterministic algorithms that halt in polynomial time with a yes answer and go into an infinite loop on a no answer. The reason for this equivalence is that an algorithm of the first type can be transformed into an algorithm of the second type trivially (by checking whether the answer is no and if so going into an infinite loop) and that an algorithm of the second type can be transformed into an algorithm of the first type less trivially (by counting how many steps it performs, as it performs them, and aborting the computation and returning no whenever the count exceeds the polynomial bound on the number of steps it should take to return a yes answer). This is all very standard. —David Eppstein (talk) 00:46, 18 August 2010 (UTC)[reply]
To clarify a potential misunderstanding: in order to perform the latter transformation, we need to know the bound on the running time of the algorithm of the second type (on yes instances). Thus an explicit algorithm of the second type does not necessarily give us an explicit algorithm of the first type, which is what made possible all this discussion.—Emil J. 09:53, 18 August 2010 (UTC)[reply]

Notable proof attempts

The "Notable proof attempts" section needs expansion. Can anyone add some based, perhaps, on http://www.win.tue.nl/~gwoegi/P-versus-NP.htm ? Based on comments in earlier threads it could include:

Jodi.a.schneider (talk) 19:41, 15 August 2010 (UTC)[reply]

I'm not convinced these really are notable. I can't find anything about them in Google news, for instance. This whole section appears to me to be nothing more than a post facto rationalization for ignoring WP:NOTNEWS. —David Eppstein (talk) 23:16, 16 August 2010 (UTC)[reply]
Maybe a separate section is not the answer then, but the article needs to cover milestones in the history of the problem somewhere. See second para of Fermat's Last Theorem for an example.Infojunkie23 (talk) 07:47, 17 August 2010 (UTC)[reply]


Slightly tangential comment: We need to be careful not to insert the WP sense of the word notable into article space. Whether the attempts are notable in the sense of the WP term of art is quite a different question from whether notable is the best word to describe them in an encyclopedia. I'm not necessarily saying it isn't the right word. Just that we all need to be on our guard not to be influenced by the WP usage when choosing words for article space. --Trovatore (talk) 10:26, 17 August 2010 (UTC)[reply]
Agreed. Actually I'm sufficiently concerned about that point that I think the word should be avoided, ceteris paribus. CRGreathouse (t | c) 14:35, 17 August 2010 (UTC)[reply]
I also agree none of these attempts seem notable, and the section should be removed. (though it's probably easier to remove it eventually, when all this settles down.) Fermat's Last Theorem is different because it has already been proved, so mathematicians can with hindsight decide what the milestones were and what were the dead ends. :-) Shreevatsa (talk) 19:45, 17 August 2010 (UTC)[reply]
  • I'd like to get rid of this section. I think it is either misconceived or in poor taste. We should retain a mention of the Deolalikar incident because it's still of some current interest and the Deolalikar biography AfD closed to merge the content here, but should retitle the section and not add other such stuff without good reason.

    The actual situation is that P vs NP, like FLT and other famous math problems, has generated a huge amount of research attempting to solve it but ending up proving lesser results (or in some cases creating research directions more important than the original problem). Researchers working on P vs NP are constantly publishing papers on whatever progress they make without claiming they actually solved P vs NP. Those are proof attempts that actually accomplish something, they're just not written up as "proof attempts". The proof attempts section currently in the article (and with its suggested expansion) is really a "list of confused researchers who incorrectly thought they had proved P!=NP" and as such it's a bit tacky. We have a list of published false theorems but that's limited to theorems that actually made it into edited journals. I don't think we need to worry about mistaken proofs that were rejected or withdrawn before publication.

    I'd also point out that while Swart, Nelson, and Deolalikar are all professional mathematicians, none of them are complexity theorists, and as such may have made mistaken claims based partly on not understanding (the way specialists do) how hard the P vs NP problem really is. In sports terms, solving P vs NP is like accomplishing a ten-foot high jump. These "attempts" are not like 8 or 9 foot jumps that didn't reach 10 feet, since when someone jumps 8 feet (which is still remarkable) they normally announce it as an 8 foot jump. Papers like Deolalikar's are more like when a professional soccer player does a 120 cm (about 4 foot) jump, thinks "ok, I guess low-profile track and field events like the high jump doesn't attract as good athletes as major sports like soccer", and announces they did a 10 foot jump, when they really had just gotten confused and thought 1 foot was 10 centimeters instead of 12 inches. Someone who can actually jump 7 feet has had a lot of high-jump practice and coaching, and as such, has a better understanding of the difficulty of reaching 10 feet and knows to check any claim very carefully. It's the same way with complexity theorists and P vs NP. 67.122.209.167 (talk) 22:40, 17 August 2010 (UTC)[reply]

  • I see the section has been renamed "attempts at proof". That is still misleading since the section is really about "erroneous claims of proof". There are many "attempts at proof" by researchers who don't make such errors, they just say (at most) "I tried such-and-such approach and it didn't work". The erroneous claims are not of much intrinsic interest and this most recent one only got a lot of attention because of some errors of judgement of certain bloggers when it first started circulating. 67.122.209.167 (talk) 04:00, 18 August 2010 (UTC)[reply]
  • I have rewritten the section and changed its title to "proof announcements". I think the text could use improvement but that it's an ok start, and I like the new approach and title better. If you change the title again, please make sure to also fix the anchor in the redirect now at Vinay Deolalikar. 67.122.209.167 (talk) 05:41, 18 August 2010 (UTC)[reply]
I have undone some of your changes, since they are mildly POV and contain a bias against such proof attempts. It's not fair to say that consensus has emerged that the proof is incorrect meaning it can't resolve the concerns or is completely useless. The proof has not been peer reviewed yet. http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/ says "Yogi Berra said, “It ain’t over til it’s over.” To judge from the discussions reported above, it ain’t over. This is so even with the passing of some days since the community has determined that the answers to the first two of Tao’s three questions which we headlined on Wednesday is “No”, and most probably likewise the third." So please don't declare final judgement prematurely. It's unfair either to say that these are not real attempts but merely "announcements". --rtc (talk) 09:34, 18 August 2010 (UTC)[reply]
Note that anchors and section names are independent. I have put there an explicit anchor so that we do not have to worry about breaking the link should the section named change. There is in fact no reason to keep a separate section just because of the redirect, the anchor can be put anywhere in the text if we choose to get rid of the section and only mention Deolalikar in passing.—Emil J. 10:05, 18 August 2010 (UTC)[reply]
Oh, nice. Thanks. 67.122.209.167 (talk) 16:46, 18 August 2010 (UTC)[reply]
I don't think Rtc's partial reversion is appropriate. First of all the section title "notable proof attempts" is really wrong, for reasons stated earlier, and even more so with the current text (even after rtc's edit) since most of the announcements on Woeginger's page are not notable. I don't understand what Rtc means by "merely announcements". If someone says "I have solved P vs NP", that is an announcement (maybe not a correct one), and that is what the section documents. And it's not "mere": "announcement" is a perfectly neutral description. If someone works on the P vs NP problem and ends up (say) inventing descriptive complexity, that is an attempt, which is not what the section is about. Second, Deolalikar's proof is really all but dead as a proof, though there's some chance of a useful idea or two emerging from it. My old wording wasn't the greatest and adding a little more nuance to it would have been fine, but I think Rtc (and to some extent Lipton) are overstating the current status of D's proof. It will only really be "over" if D. himself withdraws it, which he might never do. As Lance Fortnow explains,[8] "Deolalikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects." Now what? 67.122.209.167 (talk) 16:35, 18 August 2010 (UTC)[reply]
"If someone says "I have solved P vs NP", that is an announcement (maybe not a correct one), and that is what the section documents. I don't see what's "mere" about it--"announcement" is a perfectly neutral description." Not at all neutral. It's a description that focuses on the act of announcing "I have solved P vs NP", neglecting that there is a proof taking up quite some space compared to this mere announcement. "Second, Deolalikar's proof is really all but dead as a proof, though there's some chance of a useful idea or two emerging from it." That's your view. Fact is Deolalikar claims to have a proof and fact is there are some (notable researchers) claiming to have found invalid reasoning in this proof that is impossible to fix. But neither has Deolalikar himself acknowledged that there is a fundamental problem nor has any peer review been done to reject this proof. So we should report both views and not claim one of them to be correct. "but I think Rtc is overstating the current status of D's proof." Even if that should be true, it doesn't justify to fix this problem with nebulous statements like "consensus emerged that the proof was incorrect". Most people are probably open on that question and are ready to give Deolalikar some more time to cope with the counter-arguments before final judgement is made. "It will only really be "over" if D. himself withdraws it, which he might never do." We do not need to speculate about that. If people start writing in their blogs "Deolalikar is irrationally ignoring major lines of criticism" instead of "It ain’t over til it’s over" we can discuss that again. "Now what?" Let's stick to the facts and not declare final judgement has been made or can be foreseen. --rtc (talk) 18:19, 18 August 2010 (UTC)[reply]
  1. Yes, "announcement" focuses on the act of announcing. It is a neutral term for describing that act. The section is about announcements, precisely that. Not about proofs or attempts at proofs. It's not about (correct) proofs since no proof has been found. It's not about attempts at proofs since most of those (including very substantial ones, like Sipser's multi-year investigation of circuit lower bounds) aren't described that way in the resulting publications; as such, the whole concept of "attempts at proof" as an encyclopedic topic is misconceived. The section is about papers whose authors have purported are proofs but that haven't been accepted as such. If you've got a different word than "announcement" for that, then ok, but "attempted proofs" is really not appropriate.
  2. "Consensus emerged" is from the cited NYT article. A bit of expansion (including quoting Lipton) would be fine, and we should mention that D. has not withdrawn the claim, but frankly I think you're being a bit tendentious in saying D's proof has not been peer reviewed, given the amount of examination that's taken place and found apparently-unfixable holes. You may also be misinterpreting Lipton, whose reading of the mathematical situation is (as far as I can tell) about the same as everyone else's, but who has adopted a deferential writing style that (sort of like the Wikipedia arbitration committee's ;-)) makes it a bit too easy to confuse purely formal possibilities with plausible real-life events. FWIW, Bill Gasarch ([9] #7) has rather forcefully called for withdrawal by August 26 and says "[t]he only real news I can see happening at this point is a retraction". Gasarch's summary of the situation is pretty accurate in my opinion.
Can I ask what it will take to get you to say "it's over", if a) D. doesn't withdraw the proof (e.g. he keeps writing revised versions of the paper, like Swart did); b) nobody actually comes out in public and writes "D. is irrationally ignoring major lines of criticism" (they just stop posting about him instead); and c) the paper is not formally refereed by a journal (editors have the discretion to reject unpromising papers without bothering referees with them) so by your apparent standards it won't have been peer reviewed? I think the main TCS bloggers who have written about this affair are Aaronson, Fortnow, Gasarch, and Lipton (am I missing anyone? We could add Gowers, though great as he is, I don't think of him as a TCS guy) and I just don't see a whole lot of difference between them about the proof's mathematical prospects. 67.122.209.167 (talk) 20:22, 18 August 2010 (UTC)[reply]
1. "It's not about attempts at proofs since most of those (including very substantial ones, like Sipser's multi-year investigation of circuit lower bounds) aren't described that way in the resulting publications" That doesn't hinder us to say that they actually are attempts or have developed out of attempts. They are not mere "announcements", they are attempts to prove the thing, perhaps accompanied with such announcements, though not always. 2. "but frankly I think you're being a bit tendentious in saying D's proof has not been peer reviewed, given the amount of examination that's taken place and found apparently-unfixable holes." There's no question about that, it simply has not been peer reviewed. It has been looked at, quite carefully, by quite competent researchers, and serious problems seem to have been found. But the proof has not yet been sent to a journal and has not been formally peer reviewed in this sense. Don't be unjust. One doesn't accept affirmative arguments if outside of formal journal refereeing as peer review, so one shouldn't accept negative argumments made in such a way as peer review. "makes it a bit too easy to confuse purely formal possibilities with plausible real-life events" Besides that I do not think that a possibility can be "purely formal", you seem to have the same misunderstanding with respect to what I write. Let's make this clear: I think that the points made have very serious implications for the proof and that it can only be saved if D. comes up with some really really surprising and unexpected move. But we're on wikipedia, and our opinions don't matter. Just because we personally think the proof is dead doesn't mean we have to write the article to reflect this point of view. "Can I ask what it will take to get you to say 'it's over'," Me personally, I think that it is never over. If there is some valid proof at all, then for any invalid proof there is also some finite sequence of changes that transforms it into this valid one, and even going completely random steps might eventually coincide with one of those sequences. So it is the wrong thing to even ask such questions completely outside of the realm of computer science as "is it over"? If you want to know exactly, I am a Popperian, and I think that Proofs and Refutations makes quite some important points (though I don't want to say I like any of the other works Lakatos has written). But all that is quite irrelevant for the question what to put into this article and I think the whole discussion will be obsolete once things develop, so perhaps let's just wait and see what comes next (and not speculate on what might come next -- as you do -- and try to to anticipate it in the article). BTW, everyone with their rather hostile attitude towards D. seems to forget that it wasn't D. who put this proof on the public web and that his initial announcement wasn't public either. --rtc (talk) 21:40, 18 August 2010 (UTC)[reply]

Sorry, I don't think this is working:

  • They are not mere "announcements", they are attempts to prove the thing -- they are more than "attempts to prove the thing", they are attempts that have been proclaimed successful by their authors (i.e. announcements) without leading to general recognition of actual success. Most P/NP proof attempts (in fact all of them so far) are unsuccessful, but in the usual situation, the attempter is careful enough to recognize the failure and doesn't proclaim success, so those attempts are not listed in the section. Yet those unsuccessful attempts are generally higher quality work than the erroneously reported "successes". That's why the section title is misleading and there's not really an encyclopedic topic area like "attempted proofs" in the current sense of the article (if you really want to claim otherwise, please cite sources).

    To the extent that there is such a topic as "attempts at proof", it consists of mathematical techniques that were tried and didn't work, not papers that made erroneous claims. See Fortnow's survey article[10] section 4 ("In this section we present a number of ways we have tried and failed to prove P != NP") for what I have in mind. In fact I'd be happy to have a section like that, though "attempts at proof" is still not an ideal title for it. I'd be ok with titling the current section "proposed proofs" instead of "attempts at proof" or "proof announcements" (I always like that use of "proposed") so I'll change it to that unless you've got another suggestion.

  • The proof has not yet been sent to a journal and has not been formally peer reviewed in this sense. Don't be unjust. One doesn't accept affirmative arguments if outside of formal journal refereeing as peer review, so one shouldn't accept negative argumments made in such a way as peer review. That argument is fallacious on many levels:
    1. Your proposed symmetry between positive and negative arguments is not how things work in mathematics. We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right. By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals.
    2. In the absence of formal refereeing (which we might never hear the result of even if it does take place) we either don't write about it, or (in cases like this where we sort of have to), we go with the best info we have, which by now is almost all negative. I accept your criticism that my text went too far in making it sound like every last hope for this proof had been extinguished. I'm happy to have it revised, such as by including Lipton's quoting of Yogi Berra. Berra's quote evokes an image of a baseball team that's 20 points behind in the last inning of a game but hasn't yet formally lost, a reasonable depiction (IMO) of the status of D's proof. But your reversion (which eliminated several cited sources) makes it sound like a 50/50 proposition, and it isn't anything like that and never was. The article doesn't neutrally present the views in the available sources.
    3. Formal refereeing doesn't create a final pronouncement either in either the positive or negative direction. In the positive direction, we have a list of published false theorems that were refereed but later found wrong. In the negative direction, Perelman's proof of the Poincaré conjecture was never sent to a journal or formally refereed, but everyone thinks it's right and Perelman was offered (and declined) both the Fields medal and the Millenium prize. I don't mind too much that WP's content about Deolalikar's proof has from the beginning been sourced mostly from research blogs rather than journals, since we've (up to now) used pretty good judgment about what to cite (we've limited the selections to respectable researchers who seem to present the mainstream view). But I find it weird to use such sources one-sidedly, i.e. only when they're favorable to the proof, which is what you seem to be calling for. If we're only going to accept refereed results, we should remove mention of D's paper altogether.
  • I do agree about D not seeking publicity for the proof, which is why I worked to get his biography deleted, and I think the paragraph I wrote treated him with dignity. I didn't mention Scott Aaronson's $200K bet against the proof being fixable in the next 8 6 years,[11], or Gasarch's saying D. will stop being a serious researcher if he doesn't fix or withdraw the proof by August 26 (cited above) or Fortnow's remark about a 12 stage process (likewise), or Terence Tao's comparing the reaction to D's proof to the failure of a spam filter[12] or Tao's brutal car analogy[13] or Oded Goldreich's encouraging complexity experts to refuse to even look at proofs like this.[14] But we should take all these things into consideration when assessing how to write the neutral point of view as we are required to. The current version simply doesn't reflect the existing state of affairs.

I'm finding this conversation rather tedious and the current state of the section to be pretty bad. I may attempt another edit that tries to address all the above points (Rtc's and mine), but I wish someone else would weigh in on the discussion. 67.122.209.167 (talk) 02:00, 19 August 2010 (UTC)[reply]

I agree that "Notable Attempts at Proof" is a terrible title for the section and is certainly not neutral. I don't see how FLT having been proved makes any difference to coverage of history of a problem, unless there's now a WP:LogicalPostivism. :-) MSGJ said above "Just because not everything is known about a topic is not a reason to exclude what is known" which is exactly what I was trying to express, thank you.
Think we should include "progressive and/or notable papers submitted in relation to the problem whether right or wrong" but I'm struggling to make that encyclopaedic. The challenge with D's paper is that it hasn't been around long enough for an NPOV summary of milestones that moved us closer to a proof, even if the final paper fails as an entire proof.
Thus any mention of D should be restricted to "he's released a paper, there's widespread criticism of certain aspects, but no consensus yet. It has not been withdrawn at the time of writing. See your favourite complexity blog for latest." The current version of the article does that well.
I have had a look at a couple of survey papers and a SHORT summary of those kinds of activities definitely belongs in this article - just not sure where.Infojunkie23 (talk) 10:15, 19 August 2010 (UTC)[reply]
"they are more than "attempts to prove the thing", they are attempts that have been proclaimed successful by their authors (i.e. announcements) without leading to general recognition of actual success" Sure, then we agree. What about "claimed proofs"?
"Your proposed symmetry between positive and negative arguments is not how things work in mathematics. We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right. By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals." My symmetry argument was talking about what to consider as peer review and what not to consider peer review. It was not about assuming something to be wrong or right. Please read more carefully what I write. With respect to "how things work in mathematics[:] We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right." I can only say that this attitude is missing the point of mathematics entirely, which is not about belief in the truth of theorems or validity proofs, but about the quite entirely different activity of finding true theorems and valid proofs. People often confuse these two things, unfortunately and incorrectly assume that questions about if people should believe in it or not have anything do with mathematics. "which we might never hear the result of even if it does take place" again, we don't need to speculate. "By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals." They should be treated as not having undergone peer reviewed. That was all what I said. "Formal refereeing doesn't create a final pronouncement either in either the positive or negative direction." Again, I did not claim that. But at least it creates a judgment that that can then be mentioned in the article. "In the positive direction, we have a list of published false theorems that were refereed but later found wrong. In the negative direction, Perelman's proof of the Poincaré conjecture was never sent to a journal or formally refereed, but everyone thinks it's right and Perelman was offered (and declined) both the Fields medal and the Millenium prize." As I said, I didn't say anything like this. "But I find it weird to use such sources one-sidedly, i.e. only when they're favorable to the proof, which is what you seem to be calling for." Certainly not... I merely criticized the use of vague statements like "consensus emerged". I'm sure you are overestimating the differences of our views on what the article should look like. --rtc (talk) 14:44, 19 August 2010 (UTC)[reply]
I changed the section title to "claimed solutions", which I hope works for you. The current text is better than what was there before, though still not ideal. "Consensus emerged" is not vague and precisely describes the current situation, per numerous sources in addition to the NYT article whose citation you removed[15]: John Pavlus, Technology Review "the current consensus is that Deolalikar's approach is fundamentally flawed."[16]; Scott Aaronson, "a clear consensus has emerged that the proof, as it stands, is fatally flawed."[17]; and of course Dick Lipton, "the consensus seems to be best summarized by a recent comment here by Terence Tao"[18]. That comment was also called "magisterial" by Scott Aaronson.[19] Tao later downgraded his estimate to "no, no, and probably not",[20] and later still, "I think that the public scrutiny phase of this ms has basically been concluded."[21] Leo Gomes of Forbes magazine doesn't use the word "consensus" but says "now, the conventional wisdom is nowhere near as generous" [compared to initiallly] and describes another Tao comment as a "bitch slap".[22] Seema Singh of Mint (Indian financial newspaper affiliated with Wall Street Journal) says "computer scientists in India, fed up of their countrymen staking claims to answers as profound as P equals NP... have come together in refuting such assertions."[23] I could keep going, but what more do you want? The Mint article is pretty good and includes a discussion with Manindra Agrawal of AKS primality test fame, if that's of interest. 67.122.209.167 (talk) 01:59, 21 August 2010 (UTC)[reply]
Actually the current version[24] is pretty harsh and should be softened. 67.122.209.167 (talk) 03:42, 21 August 2010 (UTC)[reply]

further reading, references, etc.

Why is Berlekamp and Wolfe's book on Go in the "further reading" section? I remember looking at it and finding it interesting, but don't see what it has to do with the P vs NP problem. As I remember, n-by-n Go is PSPACE-complete and therefore probably outside NP.

Some other books mentioned, and some parts of the article, are about NP-completeness in general, rather than about the P vs NP problem specifically. We have a separate article about NP-completeness. Should we merge this article?

I notice that the references to the Millenium prize have been removed, except for the big template. Is that intentional? It was previously mentioned rather prominently in the article intro, which has since been re-written. I think it should at least be mentioned someplace in the article, though I could be convinced that the old version gave it too much emphasis by featuring it so prominently in the lead. 67.122.209.167 (talk) 22:44, 21 August 2010 (UTC)[reply]

I removed the Berlekamp/Wolfe book and added one by Goldreich which is more on-subject and which has drafts online. 67.117.146.38 (new address again) (talk) 08:08, 26 August 2010 (UTC)[reply]

Numerical analysis approaches?

NP problems can be translated into continuous problems - with constrains, or even just finding minimum of nonnegative polynomial. It's going out of standard combinatorial picture into numerical analysis and working literally between solutions - even finding complexity of such gradient method seams extremely difficult - it makes searching for P!=NP proof a bit hopeless. What is the status of such approaches? I couldn't find any information about it on Wikipedia - maybe it should be mentioned? —Preceding unsigned comment added by 195.43.85.90 (talk) 07:56, 23 August 2010 (UTC)[reply]

That kind of thing doesn't work so well for hard combinatorial optimization problems if that's what you're asking. Or, there is an analogous (and still open) P vs NP problem in real computation, if that's what you're asking about. The Blum-Cucker-Shub-Smale book listed in that article is excellent. 67.122.209.167 (talk) 11:37, 23 August 2010 (UTC)[reply]
I should add, there were a bunch of papers by Ted Swart in the 1980's claiming to have encoded Hamiltonian Path as a linear programming problem (solvable in polynomial time in the # of variables), thus proving P=NP. The error was that the number of required LP variables is exponential in the original problem size (proved by Yannakakis). The saga is mentioned in Woeginger's P vs NP page mentioned in the article. 67.122.209.167 (talk) 11:41, 23 August 2010 (UTC)[reply]
I've seen this Blum-Cucker-Shub-Smale book a few years ago - it's about something different: consequences of theoretical possibility of computing on real numbers. As I remember it's rather about computability and practically doesn't touch complexity. About linear programming approach - it requires huge amount of controllable constrains, but we can do it much simpler - translate it into just finding minimum of low degree real nonnegative polynomial (of linear number of variables) - just a single polynomial without any constrains (no exponential number of LP variables). For example for 3-SAT:
as (x OR y) and analogously 7 terms for triples - their sum reaches zero iff all terms are fulfilled.
Reaching local minimals should be quick - the only source of exponential complexity could be huge number of local minimas(???)195.43.85.90 (talk) 12:26, 23 August 2010 (UTC)[reply]
... but in local minimals gradient vector has all coordinates (also polynomials) zero - there is polynomially large number of such points. Gradient method for polynomials should have polynomial convergence time (??) ... where exponential complexity could come from? 195.43.85.90 (talk) 13:13, 23 August 2010 (UTC)[reply]
That doesn't sound right. When you multiply all that out, you get something of very high degree in a lot of variables and I don't see how to move around between minima or why there should be polynomially many. Simulated annealing makes some random jumps that can help in physically-inspired problems but not very hard ones that arise in (say) cryptography. I think cryptographers were dealing with this kind of attack long before P/NP was on anyone's mind. 67.117.145.46 (talk) 14:08, 23 August 2010 (UTC)[reply]
We don't multiply them, but just sum up - sum of nonnegative polynomials is zero iff all of them are zero. About simulated annealing - yes, in this form there are availible many advanced methods far from standard combinatorial picture, eventual P!=NP proof would have to consider ... but I still don't know how simple gradient method could be exponential? 195.43.85.90 (talk) 14:32, 23 August 2010 (UTC)[reply]
Hmm, maybe you're right about summing (I was thinking of a different encoding where each AND input means a multiplication). But gradient method iirc means pick a starting point, then follow gradient to a local minimum, and you probably have to check from exponentially many starting points to make sure you find all the minima. Anyway this is the wrong place for this discussion (we're only supposed to be talking about how to improve the article). It's better to ask this kind of thing at the mathematics reference desk, wp:RDMA. 67.117.145.46 (talk) 18:47, 23 August 2010 (UTC)[reply]
Gradient vector of polynomial is also made of polynomials - it cannot be zero too often - there are at most polynomial number of local minimas. And I agree it's not a place for such discussions, I only wanted to point out that there are also completely qualitatively different approaches than standard combinatorial ones and maybe it should be mentioned in the article. Cheers 195.43.85.90 (talk) 19:36, 23 August 2010 (UTC)[reply]
Yes, it might be worth looking in some optimization book and mentioning a method or two, the existence of approximation methods for problems like TSP, etc. I think in practice, heuristic SAT algorithms like DPLL don't use numerics like this. Re the gradient method, one issue is you might pick starting points A,B,C and they all lead to the same local minimum. How many tries do you have to make (and where?) before you know you have found the global minimum? Sounds like exponential. 67.117.145.46 (talk) 20:13, 23 August 2010 (UTC)[reply]
If the number of local minimums can be bounded by polynomially large number, we can extend this problem to search simultaneously for this number of 'repelling' local minimums: minimize "sum of polynomial value for each set" - "sum of squares of distances for each pair of sets". In this extended problem the degree of polynomial is unchanged and the number of variables increased polynomially. Its local minimum should contain a permutation of all local minimums of the original problem. So the exponential complexity would rather need to be somewhere in convergence of gradient methods (???). Standard: discrete approaches like DPLL are completely different - they work on concrete true/false valuations, while in continuous numerical analysis approaches we work literally between them. 195.43.85.90 (talk) 05:01, 24 August 2010 (UTC)[reply]
A multivariate polynomial can easily have an exponential number of local minima. For example, , which looks quite similar to the polynomials you consider, has local minimum at each point of the Boolean cube {0,1}n.—Emil J. 13:29, 24 August 2010 (UTC)[reply]

Empty string not handled by "formal" definition

The first paragraph of section P versus NP problem#Formal definitions for P and NP includes "If there is an algorithm ... which is able to produce the correct answer for any input string of length n in at most c·nk steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time ...". This definition fails for the empty input string. For the empty string, n=0 but it cannot be accepted in c·0k=0 time.

If you want to express the idea that the time is in O(nk) as stated later in the section, then you need to use a different bound. Possibilities include: b+c·nk, max(b,c·nk), and c·(1+n)k. If you are not picky about the value of k, you could also use (b+n)k. Which one would you-all prefer? JRSpriggs (talk) 12:58, 24 August 2010 (UTC)[reply]

It's customary to use nc + c.—Emil J. 13:03, 24 August 2010 (UTC)[reply]
Done. JRSpriggs (talk) 13:56, 24 August 2010 (UTC)[reply]
The way big-O notation was explained when I learned it was: a function f is in O(nk) iff there exists M,c such that for every n>M, we have f(n) < c·nk. That is, we care about the asymptotic (n→∞) situation, not small values of n. Isn't that the way it's always done now? 71.141.91.119 (talk) 21:23, 24 August 2010 (UTC)[reply]
Yes, but the sentence talks about all values of n (length of the string). Excluding small values would be the same as using max(b,c·nk) where b is an upper-bound on the time required to process the finite number of short strings, i.e. strings with n≤M. JRSpriggs (talk) 22:02, 24 August 2010 (UTC)[reply]
If the running time is in O(nk) then the sentence as written is obviously true. 67.117.146.38 (talk) 02:25, 25 August 2010 (UTC)[reply]
There is no O in the sentence as written. The sentence claimed the running time to be c·nk, not O(nk), and as such it was wrong. Obviously, it is written in this way in order to avoid the big-O notation for the benefit of readers who are not familiar with it.—Emil J. 09:51, 25 August 2010 (UTC)[reply]

I'm not sure why Professor Chaudhari's claimed proof is any more notable than others named in Woeginger's list. As for the links to http://dcis.uohyd.ernet.in, they seem to be intermittent, at least from the US. They're live for me at the moment. However,

  • The second reference, [23], is a clear copyright violation; it has a handwritten note:
    © Indian Academy of Mathematics
    Copy for private use only.
  • The third reference, [24], has pointers to [23] and to lecture notes. Perhaps usable as an external link, but certainly not a reference.

I should remove the copyright violation, but I don't want to edit war, and I've made 3 reverts "today" (in the past 24 hours). — Arthur Rubin (talk) 16:35, 6 September 2010 (UTC)[reply]

I agree with your analysis. As for notability, I also have doubts, though the fact that he actually managed to get it published does have some significance.—Emil J. 16:49, 6 September 2010 (UTC)[reply]
This paper seems dubious. I've left a possibly-relevant note on David Eppstein's user talk. 75.57.241.73 (talk) 09:11, 8 September 2010 (UTC)[reply]
Regarding this, it turns out that the edits by Rjlipton (talk · contribs) are not actually by R. J. Lipton. I've blocked the account for violating our username policy. —David Eppstein (talk) 16:44, 8 September 2010 (UTC)[reply]
Unlike the recent attempt, this attempt received no coverage from experts (or the blogosphere). This seems no more notable than any of those 50+ proofs in Woeginger's list. --Robin (talk) 14:48, 8 September 2010 (UTC)[reply]
Yeah, it's been reverted already, which is good. 75.57.241.73 (talk) 20:16, 8 September 2010 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:P_versus_NP_problem&oldid=383704515"