Talk:P versus NP problem

I think that verification is different from solving.take a look of bitcoin mining.but there are problems that contradicts the idea.I think the question should be "how"John kaiser (talk) 17:39, 12 April 2015 (UTC)

This article is unverified nonsense

I never had two people explain this theory the same way, everyone seems to have a different definition for it. I have some computer science classes from UM Rolla (Now Science and Technology) so I should be able to understand this, but not in the way it is currently written. Can somebody please use verifiable, peer reviewed, third party neutral sources for citations and references on this? Just saying "This is general stuff everyone should understand" is an excuse to not use citations and references. That is the same argument used to support the Creationism Theory. So I find it hard to believe this entire article, can someone help me out here? Thomas Hard (talk) 22:59, 6 May 2013 (UTC)

With all due respect, this article has 38 references, many of which are peer reviewed third party sources. Are you objecting to the reliability of any specific sources? Are you suggesting more sources should be added to some specific portion of the article? There is a single widely-accepted definition for the classes P and NP, as described quite carefully in this article, and there is no disagreement regarding this, although some people describe NP using an equivalent definition based on nondeterministic Turing machines. If there are parts you are having difficulty understanding can you point them out and explain what's confusing and if possible suggestions for improving accessibility? Thank you! Dcoetzee 01:57, 7 May 2013 (UTC)

None of it makes sense. It reads to me like Word salad instead of an academic paper. Thomas Hard (talk) 16:07, 7 May 2013 (UTC)

I understand that this article can and should be made simpler and easier to understand, but this is really challenging to do - it's already been made simpler several times, and I'm not sure how best to approach making it more accessible. More specific feedback than "none of this makes sense" would be really helpful. The comparison to an academic paper is also peculiar, since this article is already much easier to understand than most academic papers in the area of computational complexity. I do agree that citations should be provided even for facts that seem like common knowledge, and that time complexity requires a lot of improvement. Dcoetzee 22:59, 7 May 2013 (UTC)

Have you read Time complexity? I can't see that this tangle of articles is terribly clear if you're not familiar with the subject, but it's easy to check that's real, so there's no reason to disbelieve it.--Prosfilaes (talk) 17:04, 7 May 2013 (UTC)

I honestly tried to read it. It didn't make any sense either and it lacks credible verifications just like this article. I am trying to believe it, but it is written as a word salad that is very hard for me to read. I understand a lot of work went into it, I understand it is complex and hard to write about, I understand you have to read all of these other articles to get this article here. But none of the other articles make sense to me, or have proper verification citations, or in some cases just don't have enough verifiable citations or references. When I ask questions, I am told to just accept it as true and believe it. I find it hard to believe as there is not enough credible evidence for it, for me to believe it. Thomas Hard (talk) 19:50, 7 May 2013 (UTC)

Then you haven't looked if you think there isn't enough credible evidence for it. There are textbooks written on the subject; read one of them. Or take an algorithms class; Coursera offers a couple decent ones on a regular basis. Go to https://class.coursera.org/algo-003/lecture/index (you'll have to sign up and enroll in the class; hopefully it will still let you, but it usually does) and watch the videos on asymptotic analysis. Then go to https://class.coursera.org/algo2-2012-001/lecture/index (second part; same thing about enrolling) and watch the videos on NP-complete problems. I haven't actually watched it, but http://www.youtube.com/watch?v=VIS4YDpuP98 is a UC-Berkeley class lecture on the subject.--Prosfilaes (talk) 03:54, 8 May 2013 (UTC)

Look the way Math works, you are given a variable, it is unknown until you are given enough information to solve it. This article gives out a lot of unknown variables and unknown stuff, and does not give the information needed to solve for them or even understand what they are and what they do. If I gave you, for example D(cos r) as proof of something I am writing about, and I don't tell you what D or r are, or what they represent, how are you going to believe it? What if I just told you that they are 'Super Duper Imaginary Time' that it takes to solve an algorithm? Then I create an article on 'Super Duper Imaginary Time' that does not define it, nor does it explain it, you just have to accept that it is true. Would you then believe that? If you do believe it, I got a bridge for sale for you. Thomas Hard (talk) 20:11, 7 May 2013 (UTC)

I remember as a high school student seeing a college chalkboard with dx/dy something written on it and wondering why they didn't cancel the d's. I didn't jump to the conclusion that they didn't know what they were talking about. If you don't understand Big O notation, see the videos I mentioned above, or read Big O notation. You'd get farther here if you didn't jump from "I don't understand" to "unverified nonsense".--Prosfilaes (talk) 03:54, 8 May 2013 (UTC)

Clearly I don't understand. Have you read this book yet? It seems to cover some complex theories. Thomas Hard (talk) 17:56, 8 May 2013 (UTC)

I think it might help your effort to understand this material to reconsider how math works. Problems involving solving for something are important, but at its core math is generally thought of as what can be proven from a certain set of assumptions (see the article on ZFC). The P vs NP problem is about whether or not you can prove that an algorithm which can run always in polynomial bound time given the ability to branch at no cost in a certain precise way can always be rewritten to run in polynomial time (for a possibly different polynomial), but without the branching. — Preceding unsigned comment added by Kyle1009 (talk • contribs) 00:47, 11 August 2014 (UTC)

Ok I checked out the Euclidean Algorithm and it seems to me that it can be written in a simpler way. Solomon7968 (talk) 20:34, 7 May 2013 (UTC)

Thank you, this is what I wanted to see happen. I would like to see more of this. Thomas Hard (talk)

When some highly technical conjectures in the theory of algorithms get translated into simple statements ordinary humans can understand, something awful happens. Lets start with the very beginning: "Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer." I would start by asking - whats a computer got to do with this? Then the second question is, aren't specific examples of such problems such as integer factorisation not hard enough or different enough from each other that it makes it meaningless to ask this question for "every problem"? 112.80.243.227 (talk) 14:15, 2 November 2014 (UTC)

• There is no need for a computer. You can just as easily say "Can a solution that can be checked using a relatively small number of steps, also be found in a comparable number of steps?"
• The second part, that it makes sense to speak of "every problem", is part of why this topic is of such general interest. For example, "Bin packing" and "traveling salesman" seem like very different problems, both difficult. But what the proof shows is that if you could find an efficient (small number of steps) to one, then you could use that to solve the other. This is exactly what the "complete" part of NP-complete means - if you could solve this particular problem, you could also use that result to solve *all* other NP-complete problems. LouScheffer (talk) 03:35, 3 November 2014 (UTC)

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.

Popular culture

These sections used to be called "trivia", I believe. In any case, references are needed to show firstly, that the mentions are correct, and secondly, that someone in the world has thought it worth mentioning in some reliable source. Deltahedron (talk) 17:27, 8 August 2014 (UTC)

Although it does not mention the P versus NP problem, there's an interesting account by Alice Silverberg of the way in which Numbers (TV series) used mathematics here. Deltahedron (talk) 19:34, 10 August 2014 (UTC)

It is of interest that a general audience movie or TV show incorporates a mathematical problem, as such inclusions are nonexistent for most problems. It would not be encyclopedic to draw conclusions from such references, but simply presenting them is not a problem. Readers may be interested in ways the theory plays into popular culture, and an unbiased mentioning of instances of such is completely appropriate. Since such an inclusion presents no conclusion not directly supported by the very movie or TV show cited, it is just as well sourced as it could be. If anyone takes issue with this please explain why an unbiased inclusion of such instances is a problem, as there are some users who insist on removing such things. Otherwise, I feel it would help the article to achieve a consensus on this matter here and put these items back in the article. — Preceding unsigned comment added by Kyle1009 (talk • contribs)

Let me propose a test I've put forward in similar situations elsewhere:

A fictional or semifictional portrayal of an article's subject is worth noting or discussing in the article on that subject to the extent that reliable secondary sources demonstrate that the portrayal either (a) had a significant effect on the subject or (b) adds to an understanding of the subject itself, or of the subject's place in history or popular perception.

EEng (talk) 02:51, 11 August 2014 (UTC)

I agree with the basic idea there regarding what makes pop culture significant, but what I object to is the thought that a secondary source needs to make a case for the significance of the reference in order for the reference to be included. Certainly a secondary source should support any conclusion drawn from the reference. However, the purpose of an encyclopedia is to give information to the reader and allow the reader to make conclusions, not to give the reader conclusions made by secondary sources. Popular references are valid information relating to the cultural impact of the subject. It is in keeping with the idea of an encyclopedia to present this information and allow the reader to draw a conclusion. As long as the information is accurate, it should be made available to the reader for the reader's own conclusions. Secondary opinions are appropriate things to present to the reader, but are secondary to the raw information, the primary sources, as these provide the reader with the basic information needed to draw a conclusion. — Preceding unsigned comment added by Kyle1009 (talk • contribs)

Kyle, please sign your posts with ~~~~. EEng (talk) 04:45, 11 August 2014 (UTC)

EEng's standard seems to me both a good one to follow and consistent with how I've already been editing here. The TSP movie meets it. The other two, so far, do not. And the assertion that a portrayal had a significant effect or adds to the subject's place in history etc are exactly the sort of "conclusion drawn from the reference" for which we need a secondary source. Allowing the reader to draw conclusions is one thing; juxtaposing otherwise-unrelated things (like a TV series and a mathematical problem) in the hope that it might lead the reader to the conclusion that these things are related is another, and without sources such juxtapositions are problematic from the point of view of WP:SYN. —David Eppstein (talk) 04:33, 11 August 2014 (UTC)

(edit conflict) WP:INFO WP:IINFO puts it well: "To provide encyclopedic value, data should be put in context with explanations referenced to independent sources". A bullet list saying, over and over, stuff like "In John Smith's The Big Problem, spies chase a mathematician who may have proved that P=NP" doesn't give the reader anything he can draw a conclusion from. If no one else has bothered to comment on it then WP shouldn't be mentioning it at all. (And that's just a threshold test -- a local newspaper's review of a summer stock production probably wouldn't qualify either.) EEng (talk) 04:45, 11 August 2014 (UTC)

I think you mean WP:IINFO. —David Eppstein (talk) 05:02, 11 August 2014 (UTC)

You have been added to my "trusted coeditors" user group i.e. you are authorized to fix errors like that in my future sloppy posts. EEng (talk) 05:09, 11 August 2014 (UTC)

Some readers find it interesting to see what popular references there are to a problem. It is over reading into the situation to say that such references suggest anything else. Some readers find it interesting, the rest can ignore it. It is a small section at the end of the article. I think we can have a little more confidence in our readers than to assume they are led into conclusions by the statements of simple facts like that. Pop culture references are not drawing a conclusion at all in the eyes of any reasonable reader.Kyle1009 (talk) 16:10, 11 August 2014 (UTC)

This is not to mention the fact that a secondary source adds no value to these types of posts. The movie post cites a secondary source, but draws no information from it whatsoever. The source there is basically just filling an arbitrary requirement. And what source has the authority to determine cultural influence? Even when a secondary source is found, it is just someone's opinion somewhere, it is not like the source would be able to provide any meaningful justification of significance for something like this. That is why the references should simply be presented to the reader for the reader's own interpretation.Kyle1009 (talk) 16:11, 11 August 2014 (UTC)

The policy statement "To provide encyclopedic value, data should be put in context with explanations referenced to independent sources" stands, and you'll come to understand why it's that way when you have more experience on Wikipedia. It's not that secondary sources "have authority" -- it's just a threshold requirement here at WP that, as I said before, if no one else has bothered to comment then WP shouldn't be the first to do so.

As to the particular case of "The Traveling Salesman" (the movie) I disagree with DE. Recall that I said coverage in a secondary source is a threshold requirement only. Looking at the review I don't see any evidence that this film has affected the popular understanding (to the extent there is one) of P/NP. I'd suggest we remove it from the article unless sources can be found describing a sudden national dialogue on computational complexity or something. EEng (talk) 16:36, 11 August 2014 (UTC)

Please don't condescend to me, I have plenty of experience with academic material. The independent sources are the cited movie and TV shows. These references, in and of themselves, are interesting to some readers (no further explanation is needed for them to value the information). The information is completely accurate and cited to independent sources. WP guidelines need to be interpreted for specific situations, and in this situation we don't need more explanation than the original primary sources to provide interesting and unbiased material to readers.Kyle1009 (talk) 16:49, 11 August 2014 (UTC)

There's no condescension. This is not academia and the rules are different. You keep saying stuff like "we don't need more explanation than the original primary sources to provide interesting and unbiased material to readers", and that's headlong in conflict with WP:OR, WP:SYNTH, WP:PRIMARY, WP:IINFO. EEng (talk) 17:20, 11 August 2014 (UTC)

Wikipedia:Consensus is also worth a look. Deltahedron (talk) 17:55, 11 August 2014 (UTC)

None of those sources apply here. WP:OR only applies to original research, and with the material taken from primary sources with no explicit or implied conclusions, there is no original research. WP:SYNTH relates to presenting information in a manner suggestive of a conclusion of some kind, which is not the case here. In addition to the synthesis stuff, WP:PRIMARY is essentially summed up by the excerpt: "A primary source may only be used on Wikipedia to make straightforward, descriptive statements of facts that can be verified by any educated person with access to the primary source but without further, specialized knowledge." The inclusions discussed here are directly verifiable with no specialized knowledge, and so are consistent with this (in fact, plot summaries are given as a specific example of acceptable use). WP:IINFO provides four specific examples of what not to do, and none applies. The general guideline given there of not all verifiable things being pertinent does not directly apply either, because no policies directly prohibit what I am suggesting. In fact, WP:TRIV applies to pop culture sections as stated in its opening paragraph, and the article says: "This guideline does not suggest removing trivia sections, or moving them to the talk page. If information is otherwise suitable, it is better that it be poorly presented than not presented at all." This seems to imply that removal of a pop culture section because it just shows instances of pop culture references is inappropriate. — Preceding unsigned comment added by Kyle1009 (talk • contribs) 19:39, 11 August 2014 (UTC)

• You slid right over the bit where TRIV says If information is otherwise suitable, it is better that it be poorly presented than not presented at all.
• The exception for plot summaries allows plot details to be taken directly from the work in situations in which, for some reason, a plot summary is appropriate -- it isn't a free pass to include otherwise inappropriate material just because it's drawn directly from a work of fiction.
• Every time you post, you remind us of your neophyte status by messing up the indenting and failing to sign your posts with ~~~~. You should consider the possibility that you, with 50 edits starting a month ago, may not understand these policies as well as the other three participating here, with maybe 15 years' Wikipedia experience in toto. And the talk page of an article on the theory of computation is probably a bad place to assume that other editors will be amazed and overwhelmed by your extensive, detailed reasoning.

EEng (talk) 20:03, 11 August 2014 (UTC)

My point is that all you are really saying is that you don't see the inclusions as appropriate, all your sources loop back to that (you point to the "suitable" clause like that proves your point, because you are starting from the assumption that the material is not suitable). They do not in and of themselves prove your point; none of them give a reason for the inclusions being inappropriate. Your sources are therefore irrelevant to this discussion, and, if anything, they suggest that with your 15 years of WP knowledge, you can't point to a policy to directly support your position, so perhaps there is no such policy. As far as my syntax on this page goes, the goals of WP are not rocket science, I don't really need experience specifically editing WP to be able to correctly determine what is appropriate in an article and what is not. And it speaks more to your credibility than mine that you attack my reasoning without citing a single logical fallacy. — Preceding unsigned comment added by Kyle1009 (talk • contribs) 20:30, 11 August 2014 (UTC)

• For the third time, sign your posts with ~~~~ or it's gonna begin to seem like you're not interested in following basic protocol here.
• I didn't "point to the 'suitable' clause like it proves [my] point". I pointed to the "suitable" clause because it invalidates your point in invoking TRIVIA.
• Anyway, you see, this is where the irony of this discussion taking place on this particular page comes in -- you're mistaken if you think article content is decided using modus tollens and the Law of the Excluded Middle and pointing out logical fallacies and so on -- articles are not geometry exercises. And thus we come to Deltahedron's short post a little bit back, which outlines perhaps the most important policy of all: Wikipedia:Consensus. You need to work with us to find a criterion for inclusion we can all live with, not try to find little corners of guidelines that seem to support what you want. I've proposed a criterion we might use. What do you think of it? EEng (talk) 20:50, 11 August 2014 (UTC)

I was not pointing to the "suitable" clause to prove my point, I was pointing out that it showed the TRIVIA section was not proof of your point, as you originally brought up that section. I am not trying to use corners of policies, those who disagree with me are citing policies, and I am pointing out that those policies do not apply the way they are being portrayed. And as far as my use of logic goes, I sure hope decisions about articles are made using logic, how else does one make a decision? I only brought up logic specific vocab because you made an unfounded attack on my reasoning.Kyle1009 (talk) 21:30, 11 August 2014 (UTC)

All that aside, what I have been saying this whole time is that I do not agree with that criteria. It creates an arbitrary need for secondary sources when they are not needed. No interpretation of the primary sources is given, implicit or explicit, and so secondary sources are unnecessary. Requiring them only limits the inclusion of information that some readers may find interesting.Kyle1009 (talk) 21:30, 11 August 2014 (UTC)

• Sorry, not all article decisions are made via logic. Sometimes it's just intuition, and what seems right
• We've tried to broaden your perspective by pointing to related stuff, but let's get back to WP:IINFO: "To provide encyclopedic value, data should be put in context with explanations referenced to independent sources". I don't see a way around that. I think at this point we should wait to hear what others think. EEng (talk) 22:19, 11 August 2014 (UTC)

Removing something another person thinks should be there based on "intuition" or what "seems right" seems very inappropriate to me. There should at least be a reason that can be given to the editors that want to include the content. As for putting data in context with explanations, the place I pointed to earlier (WP:TRIV, under "what this guideline is not") shows that trivia (and pop culture) lists are not to be unilaterally condemned, meaning that context and explanations can be limited to something like "this is another instance of trivia/pop culture reference". Otherwise, trivia and pop culture lists would never be appropriate, contradicting the other policy. The references themselves are independent sources provided for reference. With that said, I agree, lets see what others have to say.Kyle1009 (talk) 00:13, 12 August 2014 (UTC)