Talk:P versus NP problem

If P = NP, P ≠ NPC

The diagram in the section about NP-Completeness (http://en.wikipedia.org/wiki/P_versus_NP_problem#mediaviewer/File:P_np_np-complete_np-hard.svg) shows wrongly that if P = NP, P = NPC. Proof: take the empty language Ø, a problem in P. No other language can ever be reduced to Ø, because yes-instances of that problem cannot be mapped to yes-instances of Ø. Therefore, Ø can never be in NPC because that would be every other language in NP could be reduced to it.

I say we remove the image.

What's this?

https://en.wikipedia.org/wiki/Talk:Travelling_salesman_problem#Linear_Programing_anyone.3F 2A01:119F:251:9000:8CDD:EA6D:B0B9:6C60 (talk) 09:09, 27 December 2015 (UTC)

What it is, is an unsourced claim. — Arthur Rubin (talk) 22:18, 27 December 2015 (UTC)

Graph isomorphism problem

In section 4, it says that the graph isomorphism problem is believed to be NP-Intermediate. While it could still be NP-intermediate, I don't think that it is believed to be NP-intermediate, though I am not an expert on the subject. Hasire (talk) 02:15, 23 January 2016 (UTC)

Adverbs

I removed some needless verbosity from the article. This included

1. the word "seminal" to describe a paper - we don't make judgements like that.
2. the word "essentially" in "It was essentially first mentioned". It was either first mentioned then, or it was not. The word means nothing.
3. the word "formally" in two contexts: "Informally speaking..." and "The informal term...". The term means nothing except that this is not a scientific document, something obvious and inherent in the concept of an encyclopaedia.

My changes were reverted, firstly with the nonsensical edit summary "nothing wrong with adverbs" - who ever said otherwise? And then with the claim that "Informally, P = NP means ..." is a completely different claim than "P = NP means ...". If it really meant something completely different, then you're misleading the reader. But it doesn't. The user surprisingly claimed to be "indifferent" to the use of biased words, but reverting my removal of them anyway.

I restored my changes. If the user wishes to undo them, he should give a clear justification here. 86.184.140.247 (talk) 21:50, 17 August 2016 (UTC)

1. As I noted in my edit summary, I don't care one way or the other about "seminal," and if you remove it (by itself) I will not revert. (Though it is possible for such a description to be encyclopedic, if it is the conclusion of reliable secondary sources. In fact, in this instance the description is borrowed from the reference at the end of the sentence.)
2. The word "essentially" signals that the referenced statement is not identical to the modern one; this is common for early work in any field. By itself the adverb is vague, but the very next sentence makes precise what its meaning is: Godel asked a question in the spirit of (but not equivalent to) the modern statement of P vs. NP. Without the word "essentially," the sentence is simply false.
3. As a technical article in an encyclopedia, this article contains a mix of formal (scientific, precise, technical) and informal statements; signalling which is which is an aid to the reader. Without the word "informally," a non-specialist reader might not realize that phrases like "quickly solved by a computer" are standing in for a precise, technical statement. It is my belief that computer scientists in general would object to your version, but not to the original version, of this sentence. --JBL (talk) 22:48, 17 August 2016 (UTC)

1. If you don't care either way, why did you put it back?
2. It doesn't make anything clear. In fact, it makes it less clear, which is why I removed it. Without the word "essentially", the sentence means what it should mean.
3. The article should not be written in a mixture of technical and non-technical language. It should be written such that it's accessible to the general reader. That's what encyclopaedias are for. No-one expects a "precise, technical statement", and no-one will be surprised if they find accurate but accessible text. See WP:TONE
4. It is my belief that computer scientists would not object to my version. Perhaps, rather than relying on beliefs, we could find some who would comment. 86.185.226.91 (talk) 23:23, 17 August 2016 (UTC)

I agree with JBL here: the adjective "seminal" is correct but unimportant, but all of the other adverbs are essential in conveying the correct meaning. It is not literally true that Gödel formulated this problem, but the essential ideas of the problem were present; that is what the adverb "esssentially" conveys, more concisely than I have just said it. It is not literally true that, as a piece of formal mathematics, the P vs NP problem is about whether things can be done "quickly", because "quickly" itself is not a formal concept in mathematics, but informally, that description conveys an accurate description of what the problem is taken to mean. And it is important to point out that the term "quickly" is used in an informal sense rather than itself having a precise meaning. By stripping out this nuance from the article, your changes made it wrong. —David Eppstein (talk) 23:41, 17 August 2016 (UTC)

You can express what you want to say far more clearly and far more accurately with other wordings. If you think my changes made it wrong (they didn't) then improve the wording another way. Without doubt, it needs improving. "Essentially" is just awful writing. And "seminal" is an opinion; we are not here to impart our opinions in articles. 86.185.226.91 (talk) 23:53, 17 August 2016 (UTC)

It is not *our* opinion; it is the sources' opinion. Expressing opinions is perfectly valid; not expressing opinions and sticking purely to verified mathematical fact would be a mistake. (For one thing, there are lots of encyclopedic subjects for which mathematical certainty is not possible.) We need only be careful whose opinions they are. And given that your attempted edit made the article wrong, you'll forgive me if I don't trust your judgement on what needs to be done to improve the wording. —David Eppstein (talk) 23:58, 17 August 2016 (UTC)

(Redacted) I suggest changing the awful and unclear "It was essentially first mentioned" to something better like "A version of the problem was first mentioned" or "It was first touched upon" or any number of other superior formulations, and restoring the other changes I made for the reasons I gave above. 86.184.140.247 (talk) 07:23, 18 August 2016 (UTC)

Editing

I made some changes which someone seems to object to, for reasons which are not entirely clear to me. Perhaps we can discuss things properly here. My edits were undone with the following edit summaries, which I will comment upon below.

1. Tightening the text is helpful, but in several cases this resulted in statements that are not technically true (Godel and the NP problem, for example).

2. Major is needed in the first sentence. Informally is needed since the technical term 'polynomial time' will not be intuitive to most Wiki readers. Godel's comment related but not identical. Replacing ie. by 'such' sis good

In the first one, if tightening the text is helpful, then why did the editor undo the edit in its entirety? That certainly was not helpful. And there is no indication of which statements are not technically true. Godel and the NP problem is hardly specific but presumably refers to the fact that I removed "essentially". This does not change the veracity of the statement, but merely removes an unclear word which serves no useful purpose. If Gödel "essentially" mentioned it, then he mentioned it. If you want to say something like "the general concept was first mentioned" or "an early version of the problem was mentioned" or something like that, that would also be clear. But in the clause "It was essentially first mentioned", "essentially" has no clear meaning.

In the second one: why is major needed? It has no clear meaning on its own, and one would not, I think, ever start an article saying it was a minor problem, even if it were generally considered to be so. Its importance to the field is amply demonstrated in the rest of the article. The text in the final paragraph which says " a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields." shows the reader very clearly why it is a major problem, in a way which the mere inclusion of the word "major" does not.

Everything in Wikipedia is to some extent "informal". We are not a textbook or a journal or a technical manuscript. We treat complex subjects in a way that an educated but non-specialist reader can understand. The phrase adds nothing of use to such a reader. It also has nothing to do with the technical term "polynomial time", which is not in that sentence. The term is rather nicely explained later on, and remains so whether the explanation is described as "informal" or not.

I do not understand what would motivate someone to quibble over a minor copyedit in this way, nor to undo an edit in its entirety if they only objected to some part of it. I see that in the second revert they once again restored two spaces after a comma instead of one, the entirely subjective term "seminal" and the inappropriately textbook-ish language of "Consider...". I hope they will take the time now to explain their objections properly. 222.29.61.49 (talk) 15:34, 9 October 2016 (UTC)

Addendum

I just realised that some similar issues are discussed in the section above. Someone said they didn't care about "seminal", but it was in the article when I chanced across it, so someone clearly does. Some relevant text I would like to comment on is this: "a non-specialist reader might not realize that phrases like "quickly solved by a computer" are standing in for a precise, technical statement". I am a non-specialist reader. I realise perfectly well that "quickly solved by a computer" is not a precise technical statement. How could it be? "quickly" does not have any precise definition. I assume that the sentence is written to explain what the problem is, not to rigorously define it, because that would not be the function of an encyclopaedia article. 222.29.61.49 (talk) 15:42, 9 October 2016 (UTC)

(e.c.) Please see the section immediately preceding this one. None of your edits were improvements, many were actively harmful, a blanket revert was appropriate. --JBL (talk) 15:44, 9 October 2016 (UTC)

None? Don't be absurd. You yourself agreed with one of them when it was suggested previously. And how dare you suggest that I deliberately set out to make the article worse? That is a very insulting accusation, especially when you have not bothered to explain what your objections actually are. 222.29.61.49 (talk) 17:15, 9 October 2016 (UTC)

Go away. --JBL (talk) 18:40, 9 October 2016 (UTC)

How telling! Well in the face of such absurd unpleasantness, I am out of here. I have better things to do than engage with such disgusting people. Goodbye. 222.29.61.49 (talk) 23:46, 9 October 2016 (UTC)

This is already discussed above. Please discuss per point if you disagree:

• 'major' is justified. The very first sentence should indicate the importance, to distinguish it from the many other unsolved CS problems that are not nearly so significant.
• The informal is important. 'Quickly' and 'polynomial' are not the same.
• 'Seminal' is reasonable. It was the first formal definition, has 6700 cites, and the term is used in many, many reliable sources (try google 'cook seminal complexity', without the quotes, if you doubt this.) Here is one from the ACM.
• Godel did not describe the P=NP problem. A re-write here is reasonable, but not to say he described it.

If editors discuss their reasoning, we could see if there is any concensus on these issues. LouScheffer (talk) 00:38, 10 October 2016 (UTC)

Yes, editors should discuss their reasoning, so it's a shame you triggered this unpleasant situation by reverting without explaining your reasoning. As you fail to condemn your disgusting friend who tells people to go away, I conclude that you do not feel obliged to abide by community norms. I see that you obviously don't understand what a neutral point of view is, you obviously don't feel that you should assume good faith, and you obviously don't really have an interest in improving articles. The conduct by editors here has been disgraceful. 222.29.61.49 (talk) 15:54, 10 October 2016 (UTC)

Of course this is all correct; the current version is quite good and none of the edits in question improve it. --JBL (talk) 01:05, 10 October 2016 (UTC)

You're a troll who immaturely tells people to "go away" while stalking them. This is deeply unpleasant behaviour. The current version is quite good but has a number of obvious failings. My edits clearly improved it. 222.29.61.49 (talk) 15:54, 10 October 2016 (UTC)