Talk:P versus NP problem/Archive 3

Archive 1

Archive 2

Archive 3

Consequences of proof

The statement that formal mathematical proofs can be generated in polynomial time if P=NP couldn't be more wrong. First of all, I dare you to write an algorithm that verifies mathematical proofs at all, let alone one that verifies them in polynomial time. That Stephen Cook guy has assumed that just because proving a theorem tends to seem to us humans to be harder than verifying a proof, that proving theorems must be an NP complete problem. That's like assuming that going to the moon is easy because it is easier than going to Mars, but that's a little wishy washy. So here's something that isn't wishy washy at all. Proving arbitrary theorems is undecidable! Not only that, it's the FIRST THING that was EVER proved to be undecidable! That's Godel's Incompleteness Theorem. Even if P!=NP, if proving theorems was NP complete then it would be at worst exponential, but it is already known to be undecidable, thus proving theorems can't lie in NP. And you know what? Verifying mathematical theorems is also known to be undecidable! That one goes by a different name. "The Halting Problem". Usually the halting problem is applied to computer programs, but a proof is merely an algorithm. Instead of stopping when you get to "END" or "return 0;" or "stop", or whatever your favorite computer language designates as the end of an algorithm, you stop when you get to "QED". Determining if you ever get to that line in an arbitrary proof in an arbitrary test case is precisely the statement of the halting problem. Thus formal mathematical proofs: proving them, undecidable. Verifying them, undecidable. This guy Stephen Cook is as epically wrong as confusing an angstrom with the size of the observable universe if he thinks something that has been proved undecidable is not just solvable but polynomial time solvable if P=NP when it was proved in the 1940s to be otherwise, before anyone even thought of P or NP.

In reality, the consequence of P=NP would be that you can solve all problems in a timely manner that do not fall into one of these 2 categories: 1. It takes a long time to verify a solution (e.g. the best next chess move). 2. It requires an experiment to be performed and its result observed (e.g. you must enter a password into a computer and see if the computer at the other end accepts it). And sadly, you will find that there is almost nothing useful that doesn't fall in one of these 2 categories. So no proof machine (verification undecidable, category 1), and thus no super-AI Asimovian brain robot to solve all our problems for us, no complete theory of physics or simplest and cheapest possible fusion reactor (verification requires an experiment to verify, category 2). The consequence of P=NP would be the end of public key cryptography. Simple as that. —Preceding unsigned comment added by 97.120.198.175 (talk) 02:32, 20 March 2011 (UTC)

The above comment is rather poorly informed. Proofs are verifiable (in polynomial time under reasonable encodings); that's why they're called proofs. Finding proofs (because of their unbounded possible size) is undecidable, verifying them is not. Coq and the Mizar system are examples of software that verify proofs. 75.57.242.120 (talk) 06:39, 20 March 2011 (UTC)

You seem to be confused as to what the "halting problem" and "incompleteness theorem" actually are. No one's talking about a machine whose function is "put this in, and get an answer" - that's impossible by the incompleteness theorem (which underlies the impossibility of the halting problem - if not for the incompleteness theorem, finding whether a machine halts would be as simple as running through all possible proofs of it halting or not halting). What we're talking about is "does this theorem have a proof of length t or less," which is certainly solvable, even with current techniques, in time exponential in t; after all, you don't deny that the corresponding problem for the halting problem, "does this machine halt within t steps" is solvable, do you? (If you do, I'll give you a hint - "run the machine for t steps...") If P = NP (it isn't... probably), it would be possible to run this in time polynomial in t (technically still exponential in input size), which would be able to resolve any open question whose answer has a proof of reasonable length. It's possible some of them don't, of course, or that some are undecidable, but a human researcher would do little better with those. A "proof machine," while not omnipotent, would certainly be quite powerful if P = NP. And even if you doubt that, take a gander at Karp's 21 NP-complete problems if you think the consequences would be "the end of public-key cryptography, simple as that." Twin Bird (talk) 23:00, 23 July 2011 (UTC)

Bolding

Is it just me, or is every occurrence of "P" and "NP" bolded? Should this be fixed or is this some special circumstance? Guoguo12--Talk--  23:59, 28 April 2011 (UTC)

Not every one - I see are a few non-bold P's and NP's. This should be fixed. Per WP:MOSTEXT, bold face is allowed only in few special cases, and this isn't one of them. -- X7q (talk) 10:47, 29 April 2011 (UTC)

 Done in this edit. I don't think I made any mistakes. Guoguo12--Talk--  19:31, 29 April 2011 (UTC)

I think this was an overzealous step. It is common in mathematics to use a different font face or font style for sets. In complexity theory, sets such as P and NP are often set in calligraphic or in bold letters. We obviously can't use the former for plain HTML, so I think bolding P and NP was appropriate. What do other maths folks think? Nageh (talk) 20:15, 29 April 2011 (UTC)

Well, that is why I posted here first. I've undone the edit for now. If there is an exception, it's not listed at WP:MOSBOLD. Guoguo12--Talk--  20:29, 29 April 2011 (UTC)

Ok, thanks for the quick response. I'm not sure that formatting of maths symbols needs to be covered by WP:MOSBOLD... note also that we have MOS:MATH, and there is a passing note of boldfacing of certain objects at Blackboard bold. Nageh (talk) 21:02, 29 April 2011 (UTC)

Hmm, it seems that they should be bolded. They are in the articles NP and P. Well then, this issue is resolved. Bolding is required. Thanks for clearing that up, Nageh. Guoguo12--Talk--  03:44, 30 April 2011 (UTC)

I tried looking at a few recent papers by established complexity theory researchers to see what kind of font they use for complexity classes (we should be trend-followers, not trend-setters, here). What I found was...a lot of inconsistency. Ryan Williams uses sans-serif [1]. Marius Zimand uses upright Roman [2] as does Scott Aaronson [3]. Oded Goldreich uses script [4]. Shiva Kintali uses boldface [5]. So it seems we're free to do just about anything as long as we're consistent about it. —David Eppstein (talk) 06:17, 30 April 2011 (UTC)

I personally like bolding complexity classes, since it helps a little to distinguish classes like L from variables or functions of the same name, but I think it's convenient to omit the bolding when linking them, since bold links are just a little too loud. Dcoetzee 18:32, 30 April 2011 (UTC)

P=NP sometimes

"P=NP where N=1" :-) (scroll the linked text up to page 134.) The text has other items related to the discussions in this talk page, such as "The impossibility of a proof of the impossibility of a proof." Max Longint (talk) 16:26, 6 October 2011 (UTC)

Useful Cartoon?

I am conflicted on actually editing this article, so I will ask you other editors if this cartoon would make this article friendlier to people who know of this P versus NP problem but can't handle any math (like me).

LadyJosie (talk) 16:12, 21 December 2011 (UTC)

The discussion page is loaded with math http://commons.wikimedia.org/wiki/File_talk:Relativistic_P_%3D_NP_Computation.png. Doug says he modified a Minkowski Diagram / Twin Paradox and he can make changes to the figure (MS Power Point) as might be suggested here. All I did was watch and proof English! None of the Minkowski Diagrams on Commons were fully PD. This one is. There will be a published reference, soon. I'll update here as it is published on Amazon Kindle as an e-book. LadyJosie (talk) 16:48, 21 December 2011 (UTC)

No, this cartoon doesn't belong in the article. If you can reference it and produce the reference, explaining the significance, it might be appropriate. Andrevan@ 04:51, 24 December 2011 (UTC)

No, the idea that relativistic time dilation can be used for exponential speedup in computation is not mentioned in this article, because it is highly speculative (and I'm pretty sure there are good arguments against it being possible without exponential energy). There is some discussion of such things at hypercomputation. A proper general discussion of time dilation's relation to computation would belong in another article than this one. More to the point, the terminology in this diagram is nonsensical (e.g. "start an NP calculation with my P algorithm"), to the point where I can't tell what the intended meaning was. Dcoetzee 05:26, 24 December 2011 (UTC)

No, but after publication and clarification, "yes" as an external link. As far as I can tell, Youvan is trying to describe something very trival by relating Einstein's time dilation effect to waiting for a slow "P" algo to do the work of a hypothetical, fast "NP" algo while the traveler is away, near v = c, and then returns to see that the "P" algo has finished. In the traveler's time frame, the calculation looked quick, although it might have scaled as N! or worse on the ground. In the static time frame, the calculation took a very long time. It's just the Twin Paradox combined with P v NP. Noncanonical (talk) 03:45, 31 December 2011 (UTC)

Youvan has updated his e-book to include a new reference which arrives at the same conclusion:

t_NP = t_P (1 – (v_NP ²/ c²))^0.5 . (Eq. 1) - from Youvan ISBN 978-0-9849696-0-9, he now quotes:

A similar equation can be found at http://www.hotquanta.com/twinslit.html , hosting a very nice white paper, entitled: “Historic Background & The Twin Slit Example”, by John K. N. Murphy. Noncanonical (talk) 23:12, 4 January 2012 (UTC)

Something is wrong with that hyperlink, above. I'll look into it, soon. Noncanonical (talk) 23:15, 4 January 2012 (UTC)

It seems trivial indeed to me, but it also has no relation to the P vs NP problem in particular. Of course time dilation can be used to accelerate computation from the perspective of an observer in an inertial reference frame. Given sufficient energy (and a means of overcoming technical issues) it could even be sped up by an exponential factor. But this says more about P vs EXP than P vs NP, and the same principle could give arbitrary speedup, or mere constant-factor speedup, depending on the energy invested. That's why I say this is the wrong article to discuss it, and one relating to computation time in general is more appropriate. Dcoetzee 09:22, 6 January 2012 (UTC)

Noncanonical (talk · contribs) was indef blocked after an AN discussion. --Walter Siegmund (talk) 18:46, 7 January 2012 (UTC)

Euler diagram blatantly wrong.

I'm removing the Euler diagram for reasons I've spelled out on its discussion page. Twin Bird (talk) 23:06, 23 July 2011 (UTC)

Sadly, your reasons are very mistaken. If P=NP, then every decision problem in NP (with two trivial exceptions, the problem in which the answer is always "yes" and the problem in which the answer is always "no") would become NP-complete. The reason is that, in that case, if X is any problem in NP other than these two exceptions, y is an instance of X for which the answer is "no", and z is an instance of X for which the answer is "yes", and if W is any other problem in NP, then there is an easy polynomial time many-one reduction from W to X: solve W in polynomial time and then output either y or z as appropriate. Since a polynomial time many-one reduction exists from anything in NP to X, X is NP-complete. —David Eppstein (talk) 00:00, 24 July 2011 (UTC

Why is it sadly mistaken? Artinmm (talk) 20:53, 5 June 2012 (UTC)

Well, it is sad when people editing in good faith make mistakes. —David Eppstein (talk) 22:29, 5 June 2012 (UTC)

What do you mean? Unfortunate maybe, but not unhappy or showing sadness. It is just computer science we are talking about here, right? :) 168.94.245.7 (talk) 17:13, 6 June 2012 (UTC)

"Mechanical transformation to traveling salesman"

In the section "NP-complete", there was the following sentence: For instance, the decision problem version of the traveling salesman problem is NP-complete, so any instance of any problem in NP can be transformed mechanically into an instance of the traveling salesman problem, in polynomial time.

There is little to no explanation as to how any NP-complete problem can be transformed into an instance of the Traveling Salesman problem (for instance the Knapsack problem). Can anyone edit this section to make it easier to understand?

Bluhd (talk) 20:46, 13 January 2012 (UTC)

While this was in fact true, it was not at all clear, obvious, or easy to prove. Proving it would take us too far afield from the topic at hand, so instead I've replaced it with the boolean satisfiability problem, which is proven to be NP-complete in the article Cook-Levin theorem. The fact that any problem in NP can be polynomial-time reduced to an NP-complete problem is simply part of the definition of NP-complete. Dcoetzee 21:02, 13 January 2012 (UTC)

Polynomial-time algorithms

This section says "It correctly accepts the NP-complete language SUBSET-SUM, and runs in polynomial time if and only if P = NP:". Does it correctly accept the language; and iff P=NP, run in polynomial time? The question is its running time, not its correctness, right? After reading it several times, I'm guessing so, but I'm still a bit unclear about it.--Prosfilaes (talk) 05:57, 8 February 2012 (UTC)

That is correct, and could be clarified. Dcoetzee 07:07, 8 February 2012 (UTC)

Quick check: logic in 3rd paragraph

In the 3rd paragraph it says:

"However, there is no known algorithm to find such a subset in polynomial time [...], and indeed such an algorithm cannot exist if the two complexity classes are not the same."

Shouldn't it be "[...] might not exist [...]"?

I don't know anything about P=NP, so I daren't edit the article. Could someone knowledgeable check this maybe? — Preceding unsigned comment added by 131.111.184.83 (talk) 00:18, 19 February 2012 (UTC)

No, cannot is correct. If P ≠ NP, then polynomial-time algorithms for NP-hard problems do not exist. Dcoetzee 06:24, 19 February 2012 (UTC)

Yes, but if it cannot exist wouldn't the problem already be resolved by a proof P=/=NP?Artinmm (talk) 20:51, 5 June 2012 (UTC)

It says "such an algorithm cannot exist if the two complexity classes are not the same". The two complexity classes it refers to are P and NP. If they are "not the same" then P ≠ NP. So, in other words, such an algorithm cannot exist if P ≠ NP (this is a conditional statement). I will revise it to make this clearer. Dcoetzee 00:21, 6 June 2012 (UTC)

Okay, but here is what makes more sense to me, because to state things in the affirmative is more precise than statements of exclusion. For clarification (as an example) I can say "an apple is a fruit" or I can say "an apple is not a vegetable". Which of these two versions is more precise and descriptive? To me it is clearly the first. For complete accuracy what was actually stated in the article was not "such an algorithm cannot exist if the two complexity classes are not the same". It was actually written "such an algorithm cannot exist if P ≠ NP". The affirmative version of this statement is:

"such an algorithm can only exist if P = NP 168.94.245.7 (talk) 17:05, 6 June 2012 (UTC) 168.94.245.7 (talk) 16:51, 6 June 2012 (UTC)

It's not an accurate analogy, because "an apple is a fruit" is not equivalent to "an apple is not a vegetable", whereas the two statements in discussion are logically equivalent. To me, it makes sense to use the old formulation, mainly because it states the case that is generally believed to be true, whereas your version states the case generally believed to be false.

As a side note, as a grammatical/stylistic nit, "can exist only if" is better than "can only exist if". --Trovatore (talk) 18:14, 6 June 2012 (UTC)

"Problems in protein structure prediction, are NP-complete"

Well, if protein structure prediction was NP-complete, then it would either mean that P=NP or that nature can solve NP-complete problems efficiently. Such a claim would be rather far-fetched for a simple chemical system. It could be that someone found a simple NP algorithm for solving protein folding, and in case of P=NP this algorithm would have been efficient. The statement in the article however can be understood as implying that protein structure prediction is NP-complete, which is probably false. — Preceding unsigned comment added by 82.81.32.39 (talk) 02:30, 21 August 2012 (UTC)

(1) NP-complete problems can still have easy instances as well as hard ones, (2) designing a problem and a solution together can be a lot easier than finding the solution given only the problem, and (3) the time scales over which protein folds are huge enough that even an inefficient search strategy may be able to find a solution. —David Eppstein (talk) 03:00, 21 August 2012 (UTC)

Surely nature "solves" the protein folding problem by just evolving the hamiltonian in time. Digital computers cannot do this. (We can't even solve the three body problem!) Sławomir Biały (talk) 03:10, 21 August 2012 (UTC)

(4) nature is in many ways a parallel algorithm. Nageh (talk) 18:06, 21 August 2012 (UTC)

I will say this again. Protein structure prediction can't possibly be NP-Complete, unless you believe nature can solve NP-Complete problems efficiently. Some of the confusion might stem from the definition of what protein structure prediction means. A 'theoretical' definition might be: Find the lowest energy arrangement of a given amino acid chain. I have no idea what is the complexity class of this problem, but this doesn't matter for practical protein structure prediction. In reality proteins don't have to be in minimal energy state. What they have to be is stable, that is consistently fold to the same shape. If you define protein structure prediction as the ability to predict the structure of any protein that might possibly be of any use in any organism(stable shape), then this problem must surely be polynomial, or at most BQP(highly unlikely to be beyond polynomial). — Preceding unsigned comment added by 82.81.32.39 (talk) 02:43, 27 August 2012 (UTC)

I believe the formal problem of protein structure prediction involves energy minimization, and is not solved by biological systems, only approximated well in many cases. Dcoetzee 03:09, 27 August 2012 (UTC)

Proteins evolved through highly incremental changes to the gene structure over hundreds of millions of years through a massively parallel system, one that could solve the Hamiltonian evolution problem very quickly indeed. I'd wager that the NP complete problem of finding proteins that aren't just stable and useful to an organism, but suited to their many particular tasks, could certainly be solved given these time-scales and favorable conditions. Anyway, if you are interested in pursuing such questions further, Scott Aaronson has a paper NP-complete problems and physical reality that makes for interesting reading. Sławomir Biały (talk) 12:09, 27 August 2012 (UTC)

Define "Cryptomania"

The word Cryptomania was used, but I find no definition.Bcwilmot (talk) 02:45, 5 November 2012 (UTC)

It is the name given by Impagliazzo to one of five hypothetical worlds, as stated in the immediately preceding sentence. —David Eppstein (talk) 02:47, 5 November 2012 (UTC)

Slightly misleading text in 4th paragraph?

Maybe I understand the problem incorrectly but a sentence in the third paragraph reads: "If it turned out that P does not equal NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify..."

Which to my mind, at least, seems to indicate the possibility that if P != NP there are some problems that are harder to compute than verify, but there are some problems that still might not be.

Would a clearer summary be something more along the lines of: "If it turned out that P does not equal NP, it would mean that all problems in NP (such as NP-complete problems) are harder to compute than to verify..."

I could be way off base. If so, please ignore me. — Preceding unsigned comment added by 24.106.217.162 (talk) 16:21, 29 November 2012 (UTC)

If the sentence is to make any sense at all, then “harder to compute than to verify” means “require more than polynomially longer time to compute than to verify”, and with this meaning there will always be problems in NP which are as easy to compute as to verify (namely, all problems from P). In other words, the possibility indicated to your mind in the second paragraph is correct and intended.—Emil J. 16:42, 29 November 2012 (UTC)

Bold

Please remove the bolding from the uses of P and NP. This makes reading the article horrible. If really necessary, use italics instead. --The Evil IP address (talk) 21:17, 12 December 2012 (UTC)

It's been discussed before at Talk:P versus NP problem/Archive 3#Bolding. Using boldface for complexity classes is quite common in literature. Favonian (talk) 21:24, 12 December 2012 (UTC)

status update

A book, "The Clothes' New Emperors", is also out, recording truthfully some of the events around the proof(s).

The book is in electronic form through Amazon Kindle. However, a reader won't have to purchase the book and can look at the informal version of the proof through a book preview.

In the following, the complete Chapter 1 of the book is given where the informal proof is outlined in a fictional setting.

======= Chapter 1 =======

(Redacted) - possible copyright violation. -- MST☆R ^{(Merry Christmas!)} 13:10, 22 December 2012 (UTC)

Algorithm Instructions explaining the problem and potential solutions

TRUE EQUALS FALSE 0=1 MINUS TRUE PLUS -0+ FALSE EQUALS TWO 1=2 PLUS TRUE MINUS +0- FALSE EQUALS FALSE 1=1 PLUS TRUE MINUS +0- FALSE EQUALS TRUE 1=0 0=1-0+1=2+0-1=1+0-1=0 FALSE TRUE TRUE TRUE TRUE — Preceding unsigned comment added by 63.64.64.178 (talk) 08:06, 23 April 2014 (UTC)

TSP movie

Anyone mind if I remove the external link to the Travelling Salesman movie? It looks pretty bogus. I haven't checked how it got there.

I'd also like to slow down the bot archiving. It's currently set to 30 days because there have been some flurries of activity on the talk page, like the time in 2010 when an erroneous proof got a lot of ephemeral press coverage. But the article and discussion are by now usually fairly slow-moving. Any objections? 66.127.54.40 (talk) 16:27, 3 December 2012 (UTC)

From what I've seen of the previews of the movie, it's about someone solving NP-complete problems, and the chaos it would cause in cryptography. It's not totally irrelevant. — Arthur Rubin (talk) 18:56, 22 December 2012 (UTC)

Sorry about My bothering

Hi. I am not a mathematician. I am a system analyst and I do not have any academic degrees. I found a new way for reading and storing a hierarchical structure in a database using a single loop without using a recursive algorithm. I found this technique since 2009 but I did not know that is one of must important and unsolved problems in computer science. One year later, I find that use this kinds of algorithms cloud in every kinds of hierarchical structures like nuclear chain reactions. In 2008, I design a database structure based on relativity, black holes and quantum mechanics laws and by mixing, these database structures, you can design a controlled nuclear chain reaction structure. My problem is I am living in Iran and I cannot trust anyone because it will be dangerous for him/her. Therefore, I did not publish it and did not work on this project anymore. Now, is there anyone that can help me on this? What should I do? I found out how we can use this model for summarizing every methods and developed codes in only one single method. By using a method you can connect file system and interface objects directly, because of that, we can hard code this method, and therefore, no one can change code. Indeed, we can store core of database in a chip. It is very simple and useful on huge structures like a 2PB hierarchical structure. Now my question is how I could publish it and what should I do. It designed on a simple logic but I cannot describe it as a formula. If someone cloud help me please send me an email on Arash.Rahimian@GMail.com or Arash.Rahimian@Live.com. I do not know is this a new way but I design that for solving my problems on reading a hierarchical structure very fast during my job for a company. My problem is how can I ask someone for help? No one do care about this project in my country even that company. What should I do? Please help me.

X-Virus 19:14, 10 February 2013 (UTC)

Iterative traversal of hierarchical structures is not particularly related to the P vs. NP problem, so I'm not sure you'll find help here. I would consider contacting a databases researcher in the US who publishes in the area of hierarchical databases by e-mail and describing your idea in detail to them. There is a good chance that you have either rediscovered existing work or that your technique contains an unforeseen flaw, and talking to an expert can help. You will have to be much clearer than you were here, however. Dcoetzee 20:02, 11 February 2013 (UTC)

TX for yout help. I will do that. — Preceding unsigned comment added by XVirus (talk • contribs) 15:01, 12 February 2013 (UTC)

An unverified claim

This is a new take that I haven't previously seen. Would it be appropriate to make mention of this idea? Not as a solution, but a step in an interesting direction?

https://docs.google.com/document/d/1klrDdOGsNghFnRjYvud73MZjK55J7mI9HDRgE7e4jfY/ — Preceding unsigned comment added by TajhLogosWhin (talk • contribs) 03:25, 6 June 2014 (UTC)

No. (1) It's a handful of buzzwords thrown together without even any semblance of coherent mathematical arguments, and (2) It hasn't been published as a reliable source. —David Eppstein (talk) 03:59, 6 June 2014 (UTC)

Carl Sagan argued the same thing in his novel. Could we use that as a source? I don't think any of the buzzwords need reprinting, just the equations and the point linking back to Sagan. Just a thought. — Preceding unsigned comment added by TajhLogosWhin (talk • contribs) 04:52, 6 June 2014 (UTC)

Still no. Carl Sagan said nothing about your particular crankery. —David Eppstein (talk) 05:28, 6 June 2014 (UTC)

Then you clearly never read all of his work. And seeing as you used the term, I must now find your belief that Carl Sagan did not write that to be equivalent to crankery. Should your crankery persist longer than my patience, I trust you will find this a useful source. https://en.wikipedia.org/wiki/Contact_(novel)

Please. This is not the place for it.--Prosfilaes (talk) 09:54, 6 June 2014 (UTC)

It? — Preceding unsigned comment added by 67.60.112.119 (talk) 13:48, 6 June 2014 (UTC)

Just to make my question as clear as possible: How can Carl Sagan be cited for this idea, not the author of the paper? If Sagan made advances on this matter, he ABSOLUTELY deserves recognition on wikipedia. If such a citation is not feasible, I'm willing to listen to your reasons. Until you can do more than tell me that Carl Sagan didn't work on this, which is absolutely false, I think Sagan deserves mention on this problem. — Preceding unsigned comment added by 67.60.112.119 (talk) 14:09, 6 June 2014 (UTC)

The idea has no place on Wikipedia. It has not been published in a peer reviewed journal or any credible source (and no, even if Contact says something about it, a science fiction novel is not a credible source.)--Prosfilaes (talk) 20:14, 6 June 2014 (UTC)

Reference article 21 has broken link

A correcting link would be: http://www.claymath.org/sites/default/files/pvsnp.pdf but I am a newbie here and do not know how to fix it. Jbuddenh (talk) 15:23, 7 March 2014 (UTC)

Year thanks, Mbuddenh! I have corrected the link along your suggestion, though I do not understand this problem.--Enyokoyama (talk) 17:14, 7 March 2014 (UTC)

Possible solution ?

Christopher Michael Langan (bio here in wikipedia)resently said in a radio interview that he thought he would be able to solve the problem:

https://www.youtube.com/watch?v=piE4zzZOjZc

He has previously published this article online:

Langan, Christopher M. (2001). "Self-Reference and Computational Complexity". Noesis-E, Vol. 1, no. 1.

However, he also said he was sceptic as to wether an academic outsider like himself, would be taken seriously.

I`m no mathematician, but I would think this problem could easily be solved ?

If he found the solution he could document it with video, audio, vitnesses etc, so there would be aboslutely no doubt as to when he came up with it. Then he could deliver his solution to the Clay Institute, before publishing it all online. If he could prove he had solved it, wouldn`t mathematicians around the world then be able to confirm this/prove him right ?

I guess many now automatically will conclude that Langans sceptisism is evidence that he can not solve the problem. Personally, I think we should give him the benefit of the doubt. In any case, I would encourage those who are interested in P vs NP to read Langans article.

Heyerdahl — Preceding unsigned comment added by 46.212.20.39 (talk) 10:36, 27 July 2014 (UTC)

Good luck to him, but both we and the Clay Math Institute require reliable publication of such a result, not just youtube speculation. Without that, there is no point in writing about it here because it's not something we can include in our article. —David Eppstein (talk) 16:27, 27 July 2014 (UTC)

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)

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)

Assessment comment

The comment(s) below were originally left at Talk:P versus NP problem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Comment(s)

Press [show] to view →

==A Naive Claim of Disproof== Thanks for producing such a great page. As a complete novice in this area I found the level fairly accessible. I would like some discussion may be of concrete examples of common mistakes. Here is an idea you could maybe shoot down: I am also interested in the concept of information loss on either side of equations xy = z If given z, xy is much harder to compute than the other way around one expects. The equation is not 'information symetrical', therefore one has to undertake a finding process to uncover that extra information, each side cannot be as easy as each other to compute. Let us say it is almost polynomial then go to wxy = z an increase in inbalance and computional time difference and so forth, eventually we must reach p does not equal NP??? 81.158.153.174 13:26, 20 October 2007 (UTC) Thanks for a good informative page Thanks for producing such a great page. As a complete novice in this area I found the level fairly accessible. I would like some discussion may be of concrete examples of common mistakes. Here is an idea you could maybe shoot down: I am also interested in the concept of information loss on either side of equations xy = z If given z, xy is much harder to compute than the other way around one expects. The equation is not 'information symetrical', therefore one has to undertake a finding process to uncover that extra information, each side cannot be as easy as each other to compute. Let us say it is almost polynomial then go to wxy = z an increase in inbalance and computional time difference and so forth, eventually we must reach p does not equal NP??? 81.158.153.174 13:26, 20 October 2007 (UTC)

Substituted at 20:13, 26 September 2016 (UTC)

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! 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)

Nash's description in letter to NSA preceded Gödel's letter

“Now my general conjecture is as follows: for almost all sufficiently complex types of enciphering, especially where the instructions given by different portions of the key interact complexly with each other in the determination of their ultimate effects on the enciphering, the mean key computation length increases exponentially with the length of the key, or in other words, the information content of the key ... The nature of this conjecture is such that I cannot prove it, even for a special type of ciphers. Nor do I expect it to be proven.” -- John Nash in letter to NSA, 1955

(Page 7)

If there are no objections to this claim, then appropriates edits can follow Capricio (talk) 06:36, 5 January 2017 (UTC)

References

The question posed here is certainly about computational complexity, but it is not (to my eye) obviously related to P vs. NP. Polynomiality is not mentioned, for example. --JBL (talk) 11:54, 5 January 2017 (UTC)

This is quite close to P=NP, though not directly stated, and making other common assumptions.

• A proposed decryption can be easily checked. Given a ciphertext and a plaintext, a proposed key can be checked in linear time (or at worst polynomial) in the length of the key.
• Nash is proposing that solving for the key under the same conditions (known cyphertext and plaintext) will take time time exponential in the length of the key.
• If this could be proved (and Nash is suitably pessimistic) it would show P != NP.

He does not mention NP-completeness (this might apply to a much larger class of problems), polynomiality of checking is (reasonably) assumed, and so so. So it's not exact, but it's close. LouScheffer (talk) 19:02, 5 January 2017 (UTC)

Maybe closer to the exponential time hypothesis (some NP problems require exponential time) than P≠NP (some NP problems require more than polynomial time). —David Eppstein (talk) 19:21, 5 January 2017 (UTC)

Also, he speaks of the mean time, and not the worst-case time. LouScheffer (talk) 00:05, 10 January 2017 (UTC)

OK, I added this to the lead section. To avoid too much history there, I added the section "History". Comments and changes are welcome. LouScheffer (talk) 00:39, 10 January 2017 (UTC)

Is adding a k-clause during satisfiability solving equivalent to deciding an (n-k) variable QBF?

I have long experience with sat solvers, and in practice, the equivalence appears to be true. However, I have never seen anything in formal theory about the idea. -jdpDaniel pehoushek (talk) 22:23, 9 February 2017 (UTC)

Theology aspects of P vs NP not discussed in the article?

> According to polls,[7][18] most computer scientists believe that P ≠ NP

Doesn't that poll imply atheism? Since G-d (or at least the G-d of Abrahamic Monotheism) is almighty by definition, he shall be able to read any PGP message or restore readable files from any "ransomware" computer virus infection, regardless of how strong ciphers were used or how much P is not equal to NP (a.k.a. Let there be plaintext and there was plaintext.)

Allegedly some currently existing cipher algorithms are already resistant to cracking by quantum computing, therefore one couldn't even try to sidestep the issue by claiming that G-d could build an arbitrary large sized QC to solve all the difficult problems.

On the other hand, sciences, including CS, do not have the authority to declare whether G-d exists or not. ("Scientists follow the scientific method, within which theories must be verifiable by physical experiment. On that basis, the question regarding the existence of God, for which evidence cannot be tested, definitionally lies outside the purview of modern science.") Thus a contradiction seems to arise and I would like to see an enlightening, brief treatise of the above topic included in the article. 82.131.210.163 (talk) 09:49, 25 May 2017 (UTC)

No, it seems unlikely that that is an appropriate point to mention in the article. If you can find reliable sources that make the point, then we can consider it. But I doubt you will. An omniscient and omnipotent God does not contradict P ≠ NP, because God is not restricted to what can be done on a deterministic Turing machine. --Trovatore (talk) 09:59, 25 May 2017 (UTC)

Don't be too sure P != NP

I recall seeing an argument that we should not be too sure P != NP.

The argument was by analogy to polynomials. Most polynomials we deal with are low order and in few variables. They are tame mathematical structures with few surprises. But attempts at Hilbert's tenth problem showed that polynomials in 9 or more variables have enormous mathematical power. There are polynomials that define all recursively enumerable sets, polynomials that encode the halting problem, polynomials that have zeros that cannot be proved within any particular set of axioms, and so on. They are hideously complex polynomials that no-one would ever run across by accident, but they exist.

By this argument, we deal daily with simple algorithms that are O(N^2) or O(N^3). These seem like tame mathematical entities that cannot possibly solve NP-complete problems. But we have very little intuition into what might be possible with wildly complex high order (say O(N^9) or greater) algorithms. Maybe, like polynomials, such algorithms are much more capable than you would think from low order examples.

I think this viewpoint would be interesting for the 'reasons to believe' section, but I've searched for it and been unable to find it. Does anyone else recall this argument and where it might be found? LouScheffer (talk) 03:28, 27 June 2017 (UTC)

User:Joel B. Lewis's inappropriate conduct

Stop reverting without explanation. You do not WP:OWN this article. You may discuss edits here, if you have anything to discuss. If you do not, then stop editing this article. 111.243.99.109 (talk) 13:44, 22 August 2017 (UTC)

Neutral point of view

An editor has claimed "There is nothing preventing us from putting opinions into our article as long as they are either consensus opinions (as this one is) or attributed, and properly sourced". This is utterly wrong. See for example:

• Avoid stating opinions as facts
• Prefer nonjudgmental language. A neutral point of view neither sympathizes with nor disparages its subject (or what reliable sources say about the subject)
• Strive to eliminate expressions that are flattering, disparaging, vague, clichéd, or endorsing of a particular viewpoint.

1.160.17.30 (talk) 01:40, 23 August 2017 (UTC)

I guess it can be difficult sometimes to tell if something is an opinion or a fact, and for instance a widely held scientific opinion should be stated as a fact rather than as an opinion. In this case I would say that 'seminal' is a fact rather than an opinion. I do agree though that an opinion which might have some noticeable dissent or even when there is a high degree of unanimity but it really is just a best guess should not be stated as fact but clearly attributed to someone. Dmcq (talk) 02:06, 23 August 2017 (UTC)

Improvements

Noting again the reasons for my edits, which I already explained in my edit summaries, and to which Joel B. Lewis has not had the courtesy to respond:

• [6] At the time I made this edit, the first paragraph said "The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.. Immediately adjacent to this tex was a box which contained the text "Unsolved problem in computer science: If the solution to a problem is easy to check for correctness, is the problem easy to solve?" What possible use is there in a box right next to the first sentence which entirely duplicates it?

• [7] Before I made this edit, there was a large box in the lead section, containing a list of all the articles which are in Category:Millennium Prize Problems. Apart from the visual clutter of unnecessary boxes, this adds nothing of any use because the article is already in Category:Millennium Prize Problems.

• [8] The article said "informally speaking" and referred to "the informal term quickly". This is implicit in the concept of an encyclopaedia. No article provides a formal definition for anything. It is redundant to say so, and wrongly suggests that the article cannot be trusted.

• [9] Whether or not a paper is "seminal" is an opinion, which Wikipedia has no business in stating a position on. The seminality or otherwise of articles in the academic literature is, in any case, entirely irrelevant in an encyclopaedic summary of a topic. Furthermore, the article used the wording "The precise statement...". There is no single precise statement. The indefinite article must be used.

User:Joel B Lewis has arrogantly undone these changes for no reason other than he thinks he owns the article. 111.243.99.109 (talk) 14:06, 22 August 2017 (UTC)

The formal/informal distinction is important. Most readers will have no idea that polynomial time maps to "quickly", in most cases. Also, "seminal" is important since the article is not only about the current state of the problem, but also its history. The "precise statement" is important in contrast with the informal discussions of the same points earlier by Nash and Godel.

Yes, so you define the terms you are using. There is nothing formal or informal about that. "Seminal" is an opinion. You missed the point about precise statement; it needs an indefinite article and not a definite one.1.160.17.30 (talk) 00:58, 23 August 2017 (UTC)

In terms of process, if something you think is an improvement gets reverted, it's most helpful to then point out on the talk page why you think it's an improvement, and let people comment. If you go to the history page, you will see that 58 watchers reviewed recent edits. So it's not just Joel - 58 other people reviewed his reversion, and at the very least did not feel strongly enough to revert his reversion. Raising the issue on the talk page can make this invisible argument much more visible. LouScheffer (talk) 16:05, 22 August 2017 (UTC)

Also, edit summaries like "I explained my edits; they clearly improve the article. You have not explained your edits; you are clearly acting without heed to the quality of the article." are not helpful. Clearly you think they are helpful, but it's not your opinion, nor Joel's, alone that counts - it's the community consensus. So you can explain why you believe they improve the article, but it is possible that others have different opinions and your view is not the consensus. The fact that there are many watchers, and they let the revert stand, implies it not not the community consensus that the changes are an improvement. So it's important to discuss, and not state. LouScheffer (talk) 19:05, 22 August 2017 (UTC)

My edit summary was accurate and helpful. I pointed out that I explained my edits; Joel B. Lewis arrogantly did not bother to do so. 1.160.17.30 (talk) 00:58, 23 August 2017 (UTC)

In defense of the Millenium Puzzles infobox, I have always found these kind of constructs useful in navigating wikipedia, going to specific category pages is not. I actually do agree that calling the paper "seminal" without some sort of supporting document is against wikipedia policy, although I may have missed something in a citation that supports the assertion. If it truly is a seminal work, there should be sources that can be cited to readd the statement. I actually don't like the unsolved problem box, but I readded it because I like having the link there. I could live without it though.

So you're saying that categories are not helpful for navigation? So you think all categories should be replaced with boxes? And you don't like the unsolved problem box but you put it back because you like it? 1.160.17.30 (talk) 00:58, 23 August 2017 (UTC)

On the use of the word "informal" there is nothing about an encyclopedia that would "imply" that the definitions are informal, and I would not assume the average reader would have the mathematically background to understand that implicitly. Removing that lessens the overall quality of the article, and is really a needless change. If someone misconstrues that to mean the article can't be trusted, that is fine, because as far as the formal definition of the problem goes this article cannot be trusted. GiovanniSidwell (talk) 18:13, 22 August 2017 (UTC)

The first four hits on Google books for "Cook" "seminal" "NP" all clearly support using this word: [10] [11] [12] [13]. It's not WP:PEACOCK when it's the consensus of reliable sources that it accurately describes the subject. —David Eppstein (talk) 18:19, 22 August 2017 (UTC)

I'm not disputing that it is a seminal work, it clearly is. I would just prefer to see a source for the statement in the article. And I don't believe this sort of statement fits wiki guidelines for being an obvious statement that doesn't require substantiation, since it is only obvious to people who are experts in the field. I fully support readding seminal with proper citations. GiovanniSidwell (talk) 19:43, 22 August 2017 (UTC)

Imagine replacing the word "seminal" with the word "brilliant". You think you can use the word "brilliant" in the voice of the encyclopaedia, just because it appears elsewhere? What about "poor"? What about "interesting"? You think any of these words can be used in the voice of the encyclopaedia, and the only requirement is that someone else used them? 1.160.17.30 (talk) 00:58, 23 August 2017 (UTC)

The words "brilliant" and "poor" are purely value judgments, and "interesting" begs the question "interesting to whom?". On the other hand, "seminal" has a specific factual meaning: "strongly influencing later developments". This paper did in fact strongly influence later developments, and we should say so, whether by that specific choice of words or with other wording. Such a claim needs sourcing, of course, but as I have already demonstrated that sourcing is not difficult to find. —David Eppstein (talk) 01:07, 23 August 2017 (UTC)

You misunderstand the point of the NPOV policy, and the meaning of seminal. Quoting the text that appears first in a google search for the word does not justify its use. It is a) an opinion, not a fact. b) not in any way relevant to this article. The point of the NPOV policy is to avoid exactly these sorts of utterly ridiculous arguments. 1.160.17.30 (talk) 01:11, 23 August 2017 (UTC)

I think you are the one that misunderstands NPOV. There is nothing preventing us from putting opinions into our article as long as they are either consensus opinions (as this one is) or attributed, and properly sourced. —David Eppstein (talk) 01:27, 23 August 2017 (UTC)

Right. Furthermore, none of this has changed in the past year. --JBL (talk) 01:32, 23 August 2017 (UTC)

The definition of "seminal" is "strongly influencing later developments". The paper has >7300 citations, strong factual support for this claim. It's a fact, beyond a reasonable doubt. LouScheffer (talk) 14:40, 23 August 2017 (UTC)

Still no answer to:

• Why you need a box which entirely duplicates the text of the first sentence, right next to the first sentence
• Why you need a box which entirely duplicates the function of a category.
• Why you need three "infoboxes" cluttering up the top of the article, when the infobox guidelines specifically say they should not duplicate categories and there shouldn't be more than one.
• Why you think NPOV doesn't apply to you

Nor any explanation from Joel B. Lewis of why he edits so arrogantly, in such bad faith and without heed to article quality. 1.160.17.30 (talk) 00:58, 23 August 2017 (UTC)

See WP:5P3 "Any contributions can and will be mercilessly edited", please cut the crap about "why he edits so arrogantly".

The right question is not "Why do we need" but "What is best for the encyclopaedia". Is any gain from a box an overall plus or does the addition of a box detract more from the rest of the article than it adds to the article? That is a question of judgement. I had a look at the unsolved template, it has a large number of uses of and is quite old and yet on the talk page the only suggestion about removing it is someone thinking it might encourage OR! It does not seem that other editors have considered that it should not be used but if you really do think that then nominate the template for deletion rather than just removing a particular instance of its use. Note that the infobox documentastion says an infobox is a panel that appears at the top to the right - it does not say that any panel that appears at the top to the right is an infobox. Dmcq (talk) 01:57, 23 August 2017 (UTC)

Blum's proof seems unlikely to stand

Before adding Blum's proof again, it seems very likely it will not stand. In particular, the heart of Blum's proof is Theorem 6, which says that the bounds for a monotone circuit (where we know we need exponential size) can also be applied to a general circuit. However, the Tardos function is an explicit counterexample to this theorem. It takes exponential size monotone circuits, but only polynomial size general circuits. See here. So at the very least we should wait for more analysis before adding this. LouScheffer (talk) 14:54, 25 August 2017 (UTC)

Semi-protected edit request on 8 September 2017

In the section: Does P mean "easy"? Is says that traveling salesman problem is NP-complete

Quote: There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem

But I think it is NP-hard. (It says that if you look at the wikipedia entry for that problem) It is an optimization problem, so I understand that it is NP-hard 200.40.231.41 (talk) 20:50, 8 September 2017 (UTC)

Not done: it's not clear what changes you want to be made. Please mention the specific changes in a "change X to Y" format. — nihlus kryik  (talk) 21:05, 8 September 2017 (UTC)

The words "travelling salesman problem" refer to two different things: the optimization problem mentioned in the first paragraph of the article travelling salesman problem, but also the decision problem mentioned in the third paragraph. The latter problem is a decision problem, and is NP-complete. If you had a non-clunky way to disambiguate these two in context, I'm sure people would be open to adjusting the wording. --JBL (talk) 21:30, 8 September 2017 (UTC)

Consequences of a Solution: P = NP - One-Way Functions

I recommend that we link to cryptographic hash functions instead of one-way functions. My concern stems from inconsistent use of the term "one-way function". As things stand, the reader is told that, essentially, a consequence of P=NP is that "one-way functions" would no longer be useful. This reader might then go to the relevant article only to discover that P=NP would actually imply that the functions we called one-way functions in the P versus NP article were not actually one-way functions at all and that no such functions existed in the first place (the one-way function article only talks about the strict definition of the term). Additionally, since it isn't mentioned that the term "one-way function" is only loosely applied to things like hash functions, the reader doesn't really have an obvious explanation for what this confusing situation means. Thoughts? Jwuthe2 (talk) 04:26, 9 November 2017 (UTC)

In defense of adjectives

At least one of the editors here believes the words "seminal", "informal", and "suitably" should be deleted, as these are opinions. I will argue the opposite here, explaining why I think they are helpful, well supported by reliable sources, and add value to a Wikipedia reader. Discussion of this point is of course welcome.

I agree these words are not valuable to a reader already familiar with the topic. They know already what papers are important and led to lots of future research, they understand that quickly is not formally defined, they are already impressed that Nash thought the problem of showing some problems take exponential time is really hard to prove, long before folks spent careers trying to prove it and (so far) being unable to.

But to the kind of reader who comes to Wikipedia to find out about a topic, these words are extremely helpful.

• Seminal tells the reader this a really important paper. If you want to understand the field further, start with this. In many textbooks (including ones that are extremely technical, such as Gravitation by Misner, Thorne, and Wheeler) the important results are marked in bold. Seminal is a textual way of doing this. Note that the dictionary meaning of seminal includes the example "his seminal work of chaos theory". This would be the 1890 article of Poincare, which has about 1200 cites. The paper quoted here has about 7000 cites, so seminal is well supported.
• Informal is very helpful here as well. Quickly means very different things to different scientists. Hydrogen-4, for example, decays quickly in about 10^-24 seconds. Black hole binaries decay quickly in about 10¹⁷ seconds. This is why quickly is not defined scientifically - it's relative to something, which is implied by the context. Polynomials also vary over a 10⁴¹ range, or more, but they are formally defined and not relative to a context. This distinction is helpful to the (novice) reader.
• Suitably is helpful to point out to the reader that Nash's skepticism was the result of his good intuition. The formal problem was not even well defined for two more decades, and he did not have the advantage of knowing that lots of smart people had tried to prove it for decades, without success.

The view of other editors would be interesting here. LouScheffer (talk) 18:01, 23 November 2017 (UTC)

"Informal" and "suitably" are just normal descriptive words that should be unobjectionable in any context. "Seminal" is an editorial judgement that requires reliable sourcing. But for this problem, such sourcing is easy to come by. I agree that removing all adjectives and adverbs, in a misguided sense that by doing so we are being more factual, is a mistake. It removes important information from the article, both in the form of helpful guidance for the reader ("informal") and on this subject's position in the academic literature ("seminal"). —David Eppstein (talk) 18:26, 23 November 2017 (UTC)

This is the third or fourth talk page discussion of precisely this issue in the last 16 months. There is a clear (and correct) consensus in favor of the adjectives and adverbs in question. The opposition to this consensus comes from an ip-hopping user who was banned for good reason. In this context, there is nothing to discuss, the ip editor should be treated as a run-of-the-mill vandal and be reverted on sight. --JBL (talk) 01:26, 24 November 2017 (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. — Preceding unsigned comment added by 83.84.61.92 (talk) 21:17, 29 June 2014 (UTC)

Specifying the "Hard Problem"

@Joel B. Lewis: regarding [edit [14]] I feel the phrasing "is the problem easy" gives the impression of speaking in absolutism, that only one example where the difficulty is equal would be sufficient as opposed the phrasing "must the problem be equally easy" which doesn't. I'll admit my error that the recursion is not coincidental and "problem" refers to the same "problem" on both mentions. Still I feel readable typesetting is highly undervalued. Eaterjolly (talk) 15:16, 14 June 2018 (UTC)

@Eaterjolly: It's not clear to me what typesetting has to do with anything, but I agree with you that "must" is better here and have changed the wording accordingly. --JBL (talk) 15:25, 14 June 2018 (UTC)

"If the solution to a problem is easy to check

for correctness, must the problem be easy to

solve?"

as opposed to

"If a solution is easy to check for correctness,

must the prompt be equally easy to solve?"

That is all. No real further comment. (Prettiness, etc)

-- Eaterjolly (talk) 16:14, 14 June 2018 (UTC)

That is entirely a function of your particular screen/browser/viewing environment: changing the width of the page will change how the lines break. --JBL (talk) 17:01, 14 June 2018 (UTC)

MOS:BOLD

Yesterday I carefully unbolded 267 instances of P, NP, etc. with the summary Per MOS:BOLD. Today it has been reverted, with the edit summary Per MOS:BOLD: "Mathematical objects which are sometimes written in boldface". I would argue that sometimes means exactly that. As it currently stands, even the algorithm in the section on Polynomial-time algorithms has its Ns and NPs bolded, which looks ridiculous. Obviously someone at some point performed a drive-by replace all without any thought. Even the references have been bolded!

Could you please provide other examples of mathematical articles where bolding is used hundreds of times? I very much doubt that the intention of the MOS was to bold each and every instance of a mathematical object, since it looks awful. And if you feel strongly that they should indeed be bolded then at least remove the bolding from areas other than prose. nagualdesign 17:51, 23 June 2018 (UTC)

If the mathematical notation for an object is boldface, it should be boldface every time. Internal consistency in mathematical notation is important. So your argument that it would be ok to boldface some of them but then to stop because once or twice is enough makes no sense, and in fact makes so little sense that it casts doubt on your competence to edit mathematical articles. Your usage of N (hint: this doesn't mean anything) is also a bit of a red flag. As for the correct formatting of P and NP: I have seen publications that formatted these as roman, as italic, as sans-serif (in text that was otherwise in a serif font), or as bold. I don't think I've seen them as script or blackboard bold but I wouldn't be surprised. We should pick one of those here and stick to it. Boldface is a reasonable choice but not the only choice. —David Eppstein (talk) 18:15, 23 June 2018 (UTC)

Thanks for all the ad hominems. In response to those, fuck you! Back to my original point though, if the mathematical notation for an object is boldface, it should not be boldface every time. To repeat the points I made which you seem to have skipped over, it should not be boldface within references, for reasons too obvious to be worth stating, and it should not be boldface within the algorithm, which is supposed to represent bare computer code. If you can't respond to these points in a collegial manner, please don't respond at all. nagualdesign 18:31, 23 June 2018 (UTC)

"[I]f the mathematical notation for an object is boldface, it should not be boldface every time." On the contrary, it really should. Using various typeface modifications (bolding, colors, etc.) in code and pseudocode listings is common practice, because when done well it makes them easier to read. See syntax highlighting. XOR'easter (talk) 18:36, 23 June 2018 (UTC)

Even within the titles of references and within the computer code?! This is not the same thing as syntax highlighting at all. nagualdesign 18:39, 23 June 2018 (UTC)

I've removed the bolding from all of the references, the algorithm/code, and from EXPTIME. If anyone has a problem with this please discuss it here. nagualdesign 18:59, 23 June 2018 (UTC)

I have reverted your changes, since you did not obtain anything close to a consensus first. XOR'easter (talk) 19:03, 23 June 2018 (UTC)

I asked several times specifically about the bolding within references and nobody responded. The references themselves do not use bolding^example nor does Wikipedia follow the text styling of references. In short, we don't use bolding in references. As to what you call syntax highlighting, the comments are already in italics, which is what any syntax highlighter does, and there are other instances of P and NP within the code which were not highlighted. nagualdesign 19:09, 23 June 2018 (UTC)

I wasn't entirely sure about EXPTIME, so I followed the convention currently used in that article. nagualdesign 19:11, 23 June 2018 (UTC)

All complexity classes should use the same style as each other. EXPTIME is a complexity class. It should have the same style as P and NP, whatever style we choose for them here. —David Eppstein (talk) 19:14, 23 June 2018 (UTC)

Maintaining strict consistency of notation across all of Wikipedia's mathematics and computer science articles is probably a fool's errand. But we should definitely be consistent within a given article. So, however we style P and NP here, we should do the same for #P, EXPTIME and all the rest. As for the references, the important fact is that symbols for complexity classes are mathematical notation, and we use mathematical notation in citation titles when it is part of the title. (As it happens, plenty of them use boldface, if not in their titles then in their body text; e.g., the one you just linked. Moreover, exactly reproducing the formatting of a reference's title is sometimes not possible, for example number 42, which writes the complexity classes with sans-serif text amid serif prose. We can't do that here, so the sensible way to reproduce the meaning of the title is to carry over the convention that our article itself follows.)

As for "there are other instances of P and NP within the code which were not highlighted" — no, there weren't. The other instances of the symbols P and N were variable names, not complexity classes. XOR'easter (talk) 19:23, 23 June 2018 (UTC)

Wait a minute, I thought you said that the bolding was a form of syntax highlighting? Forgive my ignorance, but which syntax highlighter do you use that takes pseudocode, recognises comments that ought to be italicized, then also recognizes complexity classes within comments and highlights them in bold?

As to the bolding of reference titles, I have left a note at the MoS asking someone with more experience to weigh in. nagualdesign 19:31, 23 June 2018 (UTC)

Knowing how intense computer people can get about building tools to automate work instead of doing work themselves, there probably is an Emacs mode which does exactly that. XOR'easter (talk) 19:38, 23 June 2018 (UTC)

At the MOS talk page, you write, "It's my understanding that references use minimal text formatting". Writing mathematical notation as mathematical notation is "minimal", in that doing anything less is doing it wrong. If the title of an article included the equation $E=mc^{2}$, we would not write it as "E = mc2". In this article, we establish the convention that the way we indicate that a particular occurrence of the letter P is an instance of mathematical notation is to bold it, and carrying that convention on into the references is the reasonable thing to do, particularly when exactly reproducing the typesetting choices of the original sources is not technically possible (e.g., when the source uses sans-serif symbols amid serif prose, as mentioned above). XOR'easter (talk) 19:50, 23 June 2018 (UTC)

For amusement's sake, I note that some of the prior editors of this article actually toned down the formatting from the original titles; reference 39 uses bold in our version but had ${\mathcal {CALLIGRAPHY}}$ in the original. XOR'easter (talk) 19:58, 23 June 2018 (UTC)

Honestly, I've been editing Wikipedia for over a decade and I'm still not entirely certain of each and every aspect of the MoS, which is why I've asked someone else to weigh in. I think you're clutching at straws though. We could easily write the reference title as E = mc². As for the syntax highlighting, comments are just formatted as comments (ie, in italics). nagualdesign 20:01, 23 June 2018 (UTC)

It is a violation of MOS:MATH to use the superscript-2 character in place of a proper superscript. And again, italics vs roman is meaningful in mathematics, so we should not change one to the other willy-nilly. —David Eppstein (talk) 20:05, 23 June 2018 (UTC)

MOS:MATH applies to article prose. It doesn't apply to references AFAIK. nagualdesign 20:08, 23 June 2018 (UTC)

MOS:MATH is, ultimately, the product of people caring an awful lot about writing mathematics properly. I don't see why we should hold text to a lower standard just because it's in the "References" section. XOR'easter (talk) 20:15, 23 June 2018 (UTC)

On Wikipedia, references have their own formatting rules which are, ultimately, the product of people caring an awful lot about writing references properly. nagualdesign 20:31, 23 June 2018 (UTC)

Writing references properly includes not changing the title. —David Eppstein (talk) 20:38, 23 June 2018 (UTC)

As I'm sure you're aware, reference titles that are all caps are routinely de-capitalized. WP uses its own house style, which does not, in fact, change the title. In the example provided earlier the proper title was "THE P VERSUS NP PROBLEM" (all caps, no bolding), which we currently render as "The P Versus NP Problem", imposing (wrongly, in my opinion) MOS:MATH. nagualdesign 21:08, 23 June 2018 (UTC)

As you have made clear that you're still unaware despite having it explained to you repeatedly, English differs from mathematics in that changing the font styling, capitalization, etc., of English is usually purely cosmetic but changing the same things in a mathematical formula changes its meaning. We can change the styling of P or NP in titles to be the same as the styling we're using in the rest of the article (that would be purely cosmetic) but we should not downcase it or change it to an inconsistent style. —David Eppstein (talk) 21:18, 23 June 2018 (UTC)

I never suggested using lowercase. I suggested changing it to a style which I believe to be consistent with the rest of Wikipedia. Your response to that has been, on the whole, to cast aspersions. Up your game, David. nagualdesign 21:36, 23 June 2018 (UTC)

Sure, if you rely on an automated system to highlight text features, it'll do it in an automatic way. That's not the point. We're people writing for people, and since we are aware of what the symbols actually mean, we can include typographic indicators of that semantic baggage. Look at any book by Donald Knuth. XOR'easter (talk) 20:10, 23 June 2018 (UTC)

So, nothing at all to do with highlighting syntax, as you originally suggested. '*smh* nagualdesign 20:31, 23 June 2018 (UTC)

No, it has everything to do with highlighting syntax. It is literally a matter of identifying bits of syntax and highlighting them. XOR'easter (talk) 20:43, 23 June 2018 (UTC)

You can keep moving the goalposts if you wish. I've had quite enough for the time being. nagualdesign 21:08, 23 June 2018 (UTC)

You have accused David Eppstein of making ad hominem attacks and me of using straw man arguments and moving goal posts. The first accusation was in error; "you are not a mathematician and therefore you are wrong" would be an ad hominem, but "your arguments suggest that you are not a mathematician" is merely an inference. (Since you also apparently mistook variable names for complexity classes — ignoring the guidance that the typographic highlighting was offering! — I would have drawn the same conclusion. I do not say this to denigrate your character or to suggest that you have nothing to contribute in this corner of Wikipedia. Rather, I am hoping, in genuine good faith, to explain how the signals you send are likely to be received. I'm sure that I would have the same problem outside the tiny area where I have some professional experience, which is one reason why there are vast stretches of this encyclopedia I've never bothered with.) As for the rest, I can only say that I've tried to argue for a consistent position, the same position all along, and that nothing I've said here was a deliberate exaggeration. In all cordiality and sincerity, I suggest that being the first to escalate from curtness to vulgarity and slinging about the names of logical fallacies is not a good look. XOR'easter (talk) 22:56, 23 June 2018 (UTC)

Pure Logic

The problem examines whether problems whose solutions can be verified quickly can also be solved quickly. Are there any academic sources on the pure logic of the problem? I am no academic, but it seems to me there are real world corollaries. For instance if one's problem was being cold the solution might be starting a fire. But just because it is easy to check if a fire is burning, doesn't necessarily mean it's easy to start a fire. But sometimes lightning strikes and through no effort of our cold being the fire is started, and the problem is solved. — Preceding unsigned comment added by 216.70.34.130 (talk) 17:28, 2 December 2017 (UTC)

No, this vague philosophizing has nothing to do with P vs. NP. --JBL (talk) 18:35, 2 December 2017 (UTC)

There are actually very strong connections between this problem and mathematical logic, though, via descriptive complexity. In particular, Fagin's theorem states that NP is the class of properties expressible in existential second-order logic, so some complexity-theoretic questions involving NP (especially whether NP = coNP) have clean formulations in logic. The logical characterizations of P itself, however, are somewhat messier. —David Eppstein (talk) 03:16, 3 December 2017 (UTC)

I had a bit of confusion with the term "verified" in this current version of the article, and being only a little bit mathy via my engineering training, thought it might help to add a link to Formal verification, since the mathy way doesn't exactly use "verify" in the same way as common American speech. If no one more mathy than me agrees, feel free to revert.68.114.32.75 (talk) 17:58, 27 December 2018 (UTC)

Physical models where it's easy to see a result, but hard to generate it (such as a hole-in-one in golf, or an atomic bomb explosion) are not difficult in the computational sense - it's easy to see how the solutions should work. What is difficult is generating the initial conditions that are known to be needed. This can be due to extreme sensitivity to initial conditions (as in golf), or conditions that are rarely obtained naturally (atomic bomb). The first is more naturally studied as chaos theory and the second as engineering. Study of P =? NP, or even a solution in either direction, would have little effect on how these problems are addressed. LouScheffer (talk) 15:24, 3 December 2017 (UTC)

Bold versus Non-Bold problem

Upon reading this article, I couldn't help but notice the awful amount of bolded instances of P and NP on it. Came here to comment about that and saw that Nagualdesign had already been bold and changed that before, being subsequently reverted. Checking several related articles (NP (complexity), NP-completeness, co-NP, co-NP-complete, NP-equivalent, NP-hardness, NP-easy, NP-intermediate and even EXPTIME itself) it can be seen that none of them follows this absurdly rigid "standard". The insistence on boldness only works as a distraction, instead of helping the reader in understanding the matter (which is, or should be, the ultimate goal of any article). Can the editors involved in this dispute please be more reasonable and accept a compromise? —capmo (talk) 17:33, 8 November 2018 (UTC)

There is no ongoing dispute, and certainly there is no possibility of accepting a compromise in the abstract. If you would like to make a proposal of something in particular, I'm sure others would be happy to discuss it. --JBL (talk) 17:52, 8 November 2018 (UTC)

Thank you for your interest. If you please take the time to read the discussion above my post, you'll see there *is* an unresolved dispute regarding the use of bold typeface in the article. I tend to agree with Nagualdesign that boldness could be avoided in most instances, just as it's done in the articles I listed as examples. —capmo (talk) 02:55, 9 November 2018 (UTC)

I assure you, as the person who both initially reverted and also who was the last w to discuss the issue with NagualDesign, there is no ongoing dispute. And there is certainly no possibility of using two different notations in this article for a single concept. --JBL (talk) 12:04, 9 November 2018 (UTC)

Sorry, my tone above is a little snippy, which is not fair: there's no way you could have known about my involvement in that discussion, that I followed it closely at the time, and the follow-up conversation on Nagual's talkpage. So let me try again with less snippiness: NagualDesign made a bold edit, which had some issues, which is why it got reverted. Your proposal is too vague for me to assess whether you understand what the issues were and are proposing to do something that avoids them. --JBL (talk) 12:13, 9 November 2018 (UTC)

The issues are two, in fact: 1. Appearance: this article looks awful the way it is now. I'm pretty sure there are other notation systems that could be used in place of bold (why not small caps p, np and exptime?); and 2. Consistency: if there is a local standard here at enwiki that is supposed to be followed on mathematical articles, then why on earth is it not being applied on all the other related articles I cited? I would appreciate if you could address these issues. —capmo (talk) 18:50, 10 November 2018 (UTC)

Small caps looks fine from the reader end (though to my eye so does bold), but it looks terrible from the editor end, unless there's some easier way to produce it than the span tags in your comment. I don't think anyone is asserting that there is (or should be) a WP-wide standard for how to refer to complexity classes, just that there should be consistency within each individual article. --JBL (talk) 19:17, 10 November 2018 (UTC)

Apologies for my tardiness, but I'd like to assure all parties that this was not settled, I simply grew tired of trying, and the fact that capmo has picked up the baton makes this an ongoing dispute.

To summarize, one side of the argument is to stick to mathematical convention, the other is to use Wikipedia's house style. Now, given the list of articles provided by capmo I hope that editors are willing to reconsider things. The question is basically, does this article correctly apply MOS:MATH?

All the best to anyone willing to work on this. I don't have anything else to add to the discussion. nagualdesign 23:30, 22 August 2019 (UTC)

...Actually, having just read through the previous discussions about this the question is really, do each of these articles correctly apply MOS:MATH? Since they appear to follow different standards I would say, probably not. (See archived discussions at MOS talk page and my talk page.) Cheers. nagualdesign 00:35, 23 August 2019 (UTC)

Re appearance and internal consistency, I think there is a third issue: consistency with the mathematical literature. As far as I can tell there are several more-or-less common conventions for writing P and NP in the literature: (1) leave them as plain text, outside of any mathematical notation, so that they always take on the font and formatting of the surrounding text (e.g. Garey&Johnson, CLRS, or Sipser); (2) put them into mathematics notation, but otherwise do not add any formatting, so that they are always non-bold italic text regardless of context (Downey&Fellows), (3) use bold italic math mode (Motwani&Raghavan, Goodrich&Tamassia), (4) use mathcal (a calligraphic math font; Lewis&Papadimitriou, Hopcroft&Motwani&Ullman), or (5) use mathsf (sans-serif math; various papers but no important textbooks that I could find, and not useful here because our text is itself usually sans). I don't recall seeing upright bold outside Wikipedia and can't find any examples on my bookshelves. We shouldn't be making up our own new conventions and notation for these things. —David Eppstein (talk) 01:33, 23 August 2019 (UTC)

Hi nagualdesign, welcome back to the discussion. I don't see any part of WP:MOS that is violated by this article (but I just browsed quickly through it looking at the most likely sections). What is missing so far is a concrete suggestion for an improvement on the status quo. (Your original bold edit was a concrete proposal; unfortunately it was not an improvement, for the reasons outlined here and elsewhere.) I actually rather like the look of small-caps, but from the editor side it is really horrible. As for David Eppstein's comments, I feel like what they mostly establish is the lack of a standard notation in the field. On a personal level, I don't like having the mathematical objects P and NP formatted in plain-text, but otherwise am agnostic; I could see a switch to simple math mode (italics) as something that might gain consensus if people really want to move away from bold. --JBL (talk) 13:05, 23 August 2019 (UTC)

Looking at the outside literature, the ACM (likely the foremost computer society) commissioned an overview of the problem specifically meant to be readable by anyone in the field. This article, referenced in our article is The Status of the P versus NP Problem, by Lance Fortnow, and uses bold for each mention of P or NP - hundreds of times throughout the article. (The ACM copy cited here is behind a paywall, but the article, with the same formatting, can be found here.) So if the ACM, on their own web site, chooses bold for classes, it's clearly an acceptable choice. Furthermore, the document was, or could have been, written in TEX or one of its variants, where complex macros mean almost no penalty for almost any style imaginable. So I believe this was a deliberate choice. I'm happy to follow this convention and leave the bold in the article. LouScheffer (talk) 02:42, 25 August 2019 (UTC)

List of sources considered reliable by Wikipedia

Does Wikipedia have such a list? Orthogeek (talk) 05:53, 22 December 2019 (UTC)

See WP:RS. But generally, for articles on academic topics like P vs NP, they should be published in peer-reviewed and reputable journals or conference proceedings. In addition, a source should be used to source something, not just tacked onto a reference list with no reason as you appear to have been doing. —David Eppstein (talk) 06:33, 22 December 2019 (UTC)

• To me, WP:RS is a list of heuristics, not a list of actual publishers.
• "[...] In addition, a source should be used to source something [...]" which I thought it did - a research paper which showed an interesting connection between the P-vs-NP question and the optimal evaluation of lambda calculus terms. Is that not "something" worthy of notice?
• The author is now a full professor whose works - over 50 of then - has been published in various "journals or conference proceedings" (I will leave determinations of reliability to yourself or other editors); the reference to the paper in question was certainly "not just tacked onto" the wiki: while I eventually found the NIH's downgrade of ResearchGate, I have yet to locate the counterpart for CiteseerX. I don't have Wikipedia's resources at my disposal.
• Since your trust in me is apparently rather low on this matter, I can only suggest downloading the paper and reading it for yourself, so you can decide if it's worthy of a Wikipedia reference - if nothing else, it does list an email address for Professor Asperti...

Orthogeek (talk) 08:32, 22 December 2019 (UTC)

On the first point: there will never be a list of valid publishers (for all sorts of good reasons), just of principles to apply. I agree with David Eppstein that the principles are easy to apply in this case. On the second point: you slapped the paper on as a link at the end of the article, you did not "use [it] to source something" (i.e., you did not make the article any better, you just used it to promote some particular link without producing any useful content or increasing the verifiability). On the third point, this is irrelevant. On the fourth point, non of this is personal or about trust, it is about wikipedia policies. Finally, as a point of local culture with no bearing on anything else, it was a very strange choice to mark your rather long comment here as a "minor edit"; that should be reserved for things that actually are minor edits (typo fixes, for example). --JBL (talk) 13:11, 22 December 2019 (UTC)

Spoken Wikipedia

In this edit 15 months ago, Wow removed a spoken version of the article that was recorded in 2013. Obviously the article has changed a lot over 7 years (diff), but I would say that the older version is not so different that it is clear to me that the spoken text is worthless. I have not seen many of these spoken links before, and I am not aware of any guidelines or policies that govern them, so I was hoping others could weigh in about whether this is a thing worth having here or not. --JBL (talk) 13:23, 4 May 2020 (UTC)

Minecraft

@Limit-theorem: Why did you remove the following (added in revision 958713733 by 2601:186:4300:71F0:493D:2BC:6E1B:63D0):

The game Minecraft has "NP is not in P!" among it's random title screen messages.

It was in the popular culture section. Does Minecraft not count as popular culture? Or is the statement false (my quick web search was inconclusive)? Or what? What does “Not helpful” mean? Brianjd (talk) 12:27, 25 May 2020 (UTC)

If there is a reliable secondary source that contains some meaningful discussion about the appearance of P vs. NP in Minecraft, then it would be very reasonable to include it. But including mentions without any source raises issues of original research and of appropriate weight. (Compare with the things currently in that section, all of which have sources that include more than a passing mention.) For similar reasons, we do not include "this appeared in an XKCD cartoon" to every article for which that is true. --JBL (talk) 15:11, 25 May 2020 (UTC)

P.S. This issue comes up a lot on this page; P vs. NP is quite famous! Here are two recent other examples: [15] [16] --JBL (talk) 15:14, 25 May 2020 (UTC)

Indeed thank you @Joel B. Lewis:. The popularity of P vs NP brings all manner of popular stories here. Limit-theorem (talk) 16:11, 25 May 2020 (UTC)

Citation To Do Items

Investigate these potential issues as reported by Citation bot:

• Y fixed: CrossRef title did not match existing title: doi:10.1145/564585.564599
  • title=SIGACT news complexity theory column 36
• Y correct: CrossRef title did not match existing title: doi:10.1016/0196-6774(87)90043-5
  • title=The NP-completeness column: An ongoing guide
• Y fixed casing: CrossRef title did not match existing title: doi:10.1137/0216051
  • title=Languages that Capture Complexity Classes
• Y link is good: Operation timed out after 5001 milliseconds with 0 bytes received For URL: https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/nash-letters/nash_letters1.pdf
• Y link is good: Operation timed out after 5001 milliseconds with 0 bytes received For URL: http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf
• Y link is good: Operation timed out after 5001 milliseconds with 0 bytes received For URL: http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf
• Y link is good: Bad Gateway error for URL https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf
• Y link is good: Did not get a title for URL http://www.win.tue.nl/~gwoegi/P-versus-NP.htm: {"url":"http://www.win.tue.nl/~gwoegi/P-versus-NP.htm","session":"tgXlQ9YXedGsiA6","items":{"10.1142/9725":"Advances in Combinatorial Optimization: Linear Programming Formulations of the Traveling Salesman and Other Hard Combinatorial Optimization Problems"}}
  • title: The P-versus-NP page
• Y google only has the hardback, this is the paperback isbn: Did not receive results from Google API search isbn:9780716710455
• Y: Citation should probably not have journal = Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science as well as chapter / ISBN 978-3-540-17219-2
• Y: Citation should probably not have journal = Algorithms and Computation as well as chapter / ISBN 978-3-540-63890-2

—¿philoserf? (talk) 16:48, 25 May 2020 (UTC)

• • @Philoserf: Some human intelligence rather than high-speed mechanical blind edits would have been better here. "SIGACT news complexity theory column 36" is not the title of that reference; it is the title of the journal concatenated with the title of the department within which the reference appears. Re "citation should probably not have journal = ...": that's because it's not a journal, it's the title of a conference proceedings. The correct response would have been to fix the parameter name mismatch, not to blank the title as you did. The same goes for the next one as well. Please be more careful in future. —David Eppstein (talk) 05:17, 26 May 2020 (UTC)

    David Eppstein, that was the title of the item at that doi. I am not making high speed mechanical blind edits. Please remain civil. —¿philoserf? (talk) 05:54, 26 May 2020 (UTC)

    The doi is the doi for an instance of a regularly-appearing department in that journal. If you actually opened and read the pdf, instead of just looking at the landing page for the doi, you would see that this instance of the department consists of an introductory paragraph by its editor, followed by the article itself, under the title given in the original citation, by the author given in the original citation. Your edits make it appear that you are just blindly following the recommendations of a bot rather than understanding the references themselves, and your reply here in which you continue to not understand the reference only strengthens that appearance. —David Eppstein (talk) 05:57, 26 May 2020 (UTC)

    David Eppstein, and yet that is not what I am doing. I did open the PDF. I followed every link. I checked each reported item. I use the bot to aid me. There is a lot of crufty stuff in our encyclopedia. I will ask you once more to expect WP:GF and to use a less accusatory vocabulary. —¿philoserf? (talk) 06:31, 26 May 2020 (UTC)

    So still no acknowledgements that your edits made the article worse rather than better, and pushed work onto other editors cleaning them up? —David Eppstein (talk) 06:41, 26 May 2020 (UTC)

No Impact On Real Computing

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

Careful consideration is required to distinguish theoretical interest from practical application. Please avoid equivocal folklore.

Real computing is physical ontology. The most common counterexample is a very simple hide-and-seek game in an exponetially large data server. Turing machines strictly disallow such random-accessibility.

Another counterexample is the exponentially large logical irreversibility utilized by practical signature functions, which are axiomatically secure, if collisions are practically negligible.

The physical resource quantity required for a problem is strictly harnessed by axiomatic subadditivity. If the knowledge of the answer can alter the external physical resource of the problem, you must ask yourself where it has gone. The only possible answer is that the external resource has physically moved to the knowledge itself. The knowledge that has the ability to change the exponential quantity of external physical resource must have the same exponential resource quantity. Without exception, NP is characterized by the exponentially large physical resource you have spent to obtain the knowledge. — Preceding unsigned comment added by Waterwizardm (talk • contribs) 10:24, 9 June 2020 (UTC)

@Waterwizardm: Besides WP:NOTAFORUM (since you failed to make an explicit suggestion to improve the article), your comment runs afoul of several points:

1. Any non-parallel program can be simulated by a universal Turing machine with only polynomial overhead, and random access only saves polynomial overhead.
2. "Axiomatically secure" – wrong; the security of a cryptographic hash function rests on it being a one-way function in practice, but for any hash function computable in polynomial time, collisions could be easily found in polynomial time if P = NP due to reduction to SAT.
3. By "exponentially large" what do you mean? You need to be precise about in terms of what you are measuring the problem size by (pseudopolynomial time is an instance of where this matters). There are "search problems" that provably require exponential time, and which are believed to not be solvable in polynomial space either–the EXPTIME-complete problems.
4. The rest of your comment is meaningless hand-waving. Use the precise, formal language used by the article if you wish to be understood. At the minimum you will need to understand my previous statements clearly, or you are in no position to be making an assertion of this sort.

By the way, your views lack verifiability by reliable sources and therefore will stay out of the article.--Jasper Deng (talk) 10:55, 9 June 2020 (UTC)

Any comments are welcome, including refutative ones.They patch my loopholes.

About the collisions. They are practically negligible or mitigable, whether polynominal or not. Not all polynominal functions are physically feasible. But that is not the point. The point here is the physical quantity of how large an irreversibility is, which is completely missing in your answer. Likewise, the paradigms you and I stand upon are completely different.

I am very sure about the correctness of my informal proof. It is simple and perfect. My first two counterexamples define a very simple and very reliable resource model. The paradigm is borrowed from the recent researches of mathematical physics. All that I have proved is that the divided subadditive quantity can never vanish in a closed system, as you say. You have to understand that this is a very simple resource-dividing game.

When you say "class" or "polynominal", they sound too sloppy to me, because they are completely irrelevant to the realistic scenarios of physically feasible computing.

See https://arxiv.org/1409.5531.pdf and See https://www.sciencedirect.com/science/article/abs/pii/S037015731500229X

By the way I intentionally tried not to use formal or professional jargons experts use. This is a very simple 'physical' truth and many non-experts can understand it. — Preceding unsigned comment added by Waterwizardm (talk • contribs) 07:44, 10 June 2020 (UTC)

— Preceding unsigned comment added by Waterwizardm (talk • contribs)

This discussion page is only for improvements to the article based on published and reliable sources. Since your contributions are unpublished, they cannot be included here. Please take them somewhere else. —David Eppstein (talk) 06:29, 10 June 2020 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

The P versus NP Page

Even if all of the attempts on this page are wrong, I still think it shows effort and ingenuity. Could this be added as an external link? Alternatively, it would be interesting to write a new section on some of the more unusual "solutions" found on this page: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm . Charles Juvon (talk) 20:03, 16 August 2020 (UTC)

This is already discussed in the article, see the section P_versus_NP_problem#Claimed_solutions. --JBL (talk) 00:56, 17 August 2020 (UTC)

Thank you. I see his page hasn't been updated since 2016. Maybe I will email him to see if he plans to update the page. Lots has happened in the last 4 years. Charles Juvon (talk) 02:45, 17 August 2020 (UTC)

"I plan to update the site in the coming fall. --Gerhard Woeginger" Charles Juvon (talk) 17:59, 17 August 2020 (UTC)

Possible addition to "reasons to believe"?

I recall seeing an argument that might be appropriate for the "reasons to believe" section, for reasons you might find P=NP (the unpopular side of the argument). It worked by analogy with polynomials, which have been around for thousands of years. Low order polynomials are well understood, and researchers largely thought higher degree polynomials could be handled by similar (though more complex) methods. However, research into Hilbert's tenth problem and similar problems revealed that higher order polynomials are much more complex, until finally the resolution of Hilbert's problems shows that even Turing completeness can be encoded into polynomials of relatively low degree (I think the original proof used 13th degree polynomials). For P==NP?, by analogy, we have the same state of understanding for algorithms that existed for millennia for polynomials. We have lots of experience with algorithms of low orders, such as N^2 and N^3, which we understand fairly well, and we think of higher order algorithms as more or less the same, just slower. But perhaps the theoretical power of higher order algorithms is not yet understood. In particular, by analogy with polynomials, they could be dramatically more expressive than lower order algorithms, and there could perhaps be some algorithm of finite order that can solve NP problems, just as 13th degree polynomials can encode any mathematic problem.

I've been unable to re-find this argument on the web. Does anyone else recall it and remember where they saw it? LouScheffer (talk) 14:16, 18 September 2020 (UTC)

Would a protein folding solution be equivalent to solving this problem?

To quote the article:

"Many other important problems, such as some problems in protein structure prediction, are also NP-complete."

Will Alphafold be considered a "solution" or simply progress? — Preceding unsigned comment added by 184.105.253.195 (talk) 18:45, 30 November 2020 (UTC)

No, AlphaFold does not constitute a solution to this problem nor does it constitute progress on it. There are a variety of reasons for this, but most importantly AlphaFold does not solve the problem. It approximates the solution. --Stellaathena (talk) 16:05, 3 December 2020 (UTC)

Today's round of P=NP crankery

For how the reference from this edit (added by User:Xexeo, cleaned up by User:LouScheffer, and removed by User:JayBeeEll) could have appeared to be published in a reputable journal, see this twitter post from a member of the editorial board. The paper itself is no longer accessible, replaced by a placeholder page. —David Eppstein (talk) 21:47, 19 July 2021 (UTC)

Although I fully expected an explanation like this, I was half hoping for "Obscure grad student finds O(N³⁶) algorithm for 3-SAT, throwing computer science theory into chaos." Of course I'm not a theoretical computer scientist, so I'm free to think this. LouScheffer (talk) 22:03, 19 July 2021 (UTC)

Thanks, David, I was wondering what went wrong. I presume the article was just the latest revision of https://arxiv.org/abs/1004.3702 . --JBL (talk) 22:18, 19 July 2021 (UTC)

If we ever do get "Obscure grad student finds O(N³⁶) algorithm for 3-SAT, throwing computer science theory into chaos", I'd expect it to be heralded by a special add-on session to FOCS or STOC, a one-or-two-year wait, and then a paper in JACM, not by the appearance of a publication in a mid-level theory journal. —David Eppstein (talk) 23:58, 19 July 2021 (UTC)

Not to mention Science, Nature, and the New York Times, all of which had articles when Perlman solved the Poincaré Conjecture, another of the Clay Millennium problems. And this one's easier to explain. LouScheffer (talk) 00:53, 20 July 2021 (UTC)

Possible new introduction?

Here is a new introduction proposed recently. I feel this is too wordy for a lead paragraph, but would be very interested in other editor's opinions. A few months ago we moved example problems out of the lead, and into "examples".

Every problem as defined in theoretical computer science has sizes and the notion of quickness is defined relative to the size of the problem. There are generally many different instances for a size of the problem. For example, consider a very simple problem, Subset-Sum, the problem of deciding whether given $n$ integers and another integer $m$, whether any of the integers of the $n$ integers will sum to $m$. We measure the size of this problem by the number of integers $n$. All distinct sets of integers $n$ and a number $m$ are different instances of this same size. The entirety of the Subset-Sum problem is considered to be all of the instances for all sizes $n$. The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm which solves the problem instance (as opposed to, say, exponential time). For example, the best known algorithms for Subset-Sum currently require brute force searching through exponentially many possible sums which may add to $m$ which is an exponential number of steps as a function of $n$ and hence we would not say we know how to solve Subset-Sum quickly. The general class of questions for which some algorithm can provide an answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. For example, in the case of Subset-Sum, for any instance which does have a sum in it to $m$, if I gave you the numbers which summed to $m$, it would be very easy (“quick” or polynomial-time), to check that it was the case. The class of questions for which an answer can be verified in polynomial time is NP, which stands for "nondeterministic polynomial time".

Comments more than welcome. LouScheffer (talk) 23:51, 13 August 2021 (UTC)

In addition to being far too wordy for the lead, it is factually incorrect. It is not true that "the best known algorithms for Subset-Sum currently require brute force searching". It is a common misconception of the P vs NP problem that P ≠ NP would imply the optimality of brute force search; however, there are many other techniques known in exponential-time algorithmics and many problems (including subset sum) for which faster algorithms than brute force search are known. We should not encourage that misconception. —David Eppstein (talk) 00:28, 14 August 2021 (UTC)

In particular, the algorithm of Schroeppel and Shamir for Subset-Sum is much faster than brute force (though still exponential in the size of the input, of course). LouScheffer (talk) 00:54, 14 August 2021 (UTC)

References

Is "at least 53 of these must be wrong" original research?

In the section P versus NP problem#Claimed solutions, an editor believes the statement "At least 53 of these must be wrong" is OR (original research). But Wikipedia:These are not original research states that "Any relatively simple and direct mathematical calculation that reasonably educated readers can be expected to quickly and easily reproduce." is not OR.

By my thinking, determining at least 53 must be false falls under this categorization. The four categories are mutually exclusive, which I believe is simple and direct - i.e., if there is a proof that P=NP, then the other proofs (P != NP, it's unprovable, it's undecidable) must be wrong.

Of course, just because I think this is simple and direct does not mean everyone else thinks the same. Any opinions? LouScheffer (talk) 13:59, 19 August 2021 (UTC)

Personally I think that the greatest sin here is unnecessarily and badly explaining a joke, rather than WP:OR. (Badly, because in fact all the proofs on the list are wrong or meaningless.) I personally would not have restored the sentence that you did, but also I did not feel strongly enough about it to revert you. --JBL (talk) 16:49, 20 August 2021 (UTC)

References

I can guarantee it is possible to answer certain intractable problems correctly but impossible to manifest solution to impact minus a computer to speed up manual form of programmer minus implement of/into program/computer. Regardless of reference. Sorry.

Gerhard J. Woeginger's list

The article says that "Gerhard J. Woeginger maintains a list that, as of 2018, contains 62 purported proofs of P = NP, 50..." Yet The list as of 2016 on [17] had as many as 116 in total and there has been no change to the list since. Limit-theorem (talk) 20:16, 18 August 2021 (UTC)

It is just a refinement: 62 + 50 + 1 + 2 = 115, with one of the listed proofs a valid proof that a certain strategy can't work. It would be worth trying to find out whether this project is permanently moribund, though. --JBL (talk) 16:50, 20 August 2021 (UTC)

Someone should add that most Computer Scientists believe NP≠P in the introduction

I think there should be some mention of the general belief or consensus that NP≠P and that hard problems such as the traveling salesman problem are not easily solvable in deterministic polynomial time. This would be helpful for the general reader to get an overview of the current state of the concept in the introduction. ScientistBuilder (talk) 22:08, 13 October 2021 (UTC)ScientistBuilderScientistBuilder (talk) 22:08, 13 October 2021 (UTC)

This is already in the lede: " If it turns out that P ≠ NP, which is widely believed, it would mean..." LouScheffer (talk) 00:14, 15 October 2021 (UTC)