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 is P versus NP

Has anybody attempted to find out whether "P versus NP" it itself either a P or an NP problem? — Preceding unsigned comment added by 81.143.89.182 (talk) 09:56, 19 June 2015 (UTC)

that doesn't make sense, unless u mean "given a problem, is it in P? also, is it in NP?", which sound like not even computable. — Preceding unsigned comment added by 157.181.96.232 (talk) 14:25, 21 August 2015 (UTC)

I think the question being asked, is this: given a correct proof that p==np, could a computer algorithm (of complexity class p) be written to verify that proof? If so, what is the complexity of programming a theorem proving system that could *itself* discover the proof that p==np? In other words, is the complexity of writing a theorem-proving-system, capable of proving unsolved problems like whether p==np, of complexity level p, or of complexity level np, or of complexity level strong AI. Methinks it is definitely in the third category, but maybe there is a proof that the question-of-whether-p-equals-np is equivalent to the complexity of the travelling salesman problem. I'm not sure about the (distinct) question of the complexity-of-the-algorithm-that-could-verify-some-hypothetical-proof-that-p-equals-np, but I suspect that ... iff we presume the proof exists ... the verification-algorithm would definitely be in the p-or-the-np class, and per our assumptions, would be in the p class of complexity. 75.108.94.227 (talk) 21:41, 15 September 2015 (UTC)

one-way function

Aside from being an important problem in computational theory, 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.

I think this is wrong. The proof that p==np , would absolutely revolutionize all those fields. The proof that p!=np ... would be an important step ... that would probably require mathematics we don't currently have, or at least, ways of utilizing mathematics we already have but have not figured out fully enough. But I don't believe that, since we already know it to be true in practice, proving that "NP is way harder than P" will somehow have profound implications in philosophy and economics. Depending on the *details* of the p!=np hypothetical proof, there *might* be profound implications for algorithms/AI/crypto/math/etc, but even that is not guaranteed. Is there anybody that knows a *source* which predicts that proving p!=np (as opposed to proving p==np) would have profound consequences, outside of mathematics and into philosophy/economics/etc? Thanks, 75.108.94.227 (talk) 21:41, 15 September 2015 (UTC)

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! 222.29.61.49 (talk) 23:46, 9 October 2016 (UTC)