Talk:P versus NP problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Computing (Rated B-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Computer science (Rated B-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Mathematics (Rated B-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
High Importance
 Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
WikiProject Spoken Wikipedia
WikiProject icon This article is within the scope of WikiProject Spoken Wikipedia, a collaborative effort to improve the coverage of articles that are spoken on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 

If P = NP, P ≠ NPC[edit]

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[edit]

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[edit]

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[citation needed] 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?[edit]

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[edit]

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[edit]

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)