Talk:P versus NP problem/Archive 2

Archive 1

Archive 2

Archive 3

Semi-protect this article?

Does anyone else feel that the article might need to be semi-protected due to constant vandalism (by IPs)? --Robin (talk) 00:31, 16 December 2009 (UTC)

My experience with requesting it via the official channel WP:RPP is it will be denied at this time. Got any admins in your back pocket? ;-) Pcap ping 00:58, 16 December 2009 (UTC)

But apparently I do. ;-) Pcap ping 01:06, 16 December 2009 (UTC)

No. I believe protecting goes against the spirt of wikipedia. See the pillars. Do you not agree? I am all for fairness, progress and equality. Are you for these three things? If you are why do you want to prevent people from contributing? Thank you, a student! 01:17, 16 December 2009 (UTC) —Preceding unsigned comment added by Juicer701 (talk • contribs)

Juicer, please quit posting nonsense here. I admit the (fairly remote, I think) possibility that your additions are not nonsense, but if they aren't, they're so hard to read that they might as well be. In that case, please rewrite them in some comprehensible format. --Trovatore (talk) 01:23, 16 December 2009 (UTC)

I think one of the problems is that a lot of vandalism goes to the talk page, and WP:PROTECT (understandably) says that "A page and its talk page should not both be protected at the same time". So unfortunately semi-protection would not solve the problem. — Miym (talk) 01:31, 16 December 2009 (UTC)

On balance it's probably better, given the choice, to have the vandalism on the talk page, because here it's less likely to harm Wikipedia's reputation among readers looking up P vs NP. --Trovatore (talk) 01:44, 16 December 2009 (UTC)

Yeah, I also agree that the article should be semi-protected instead of the talk page, if only one can be protected. Most casual readers probably never read the talk page at all. --Robin (talk) 01:51, 16 December 2009 (UTC)

How about trying to get the article semi-protected again? It gets vandalized almost everyday by IP editors. The recent page history almost entirely consists of users reverting IP edits. --Robin (talk) 01:11, 25 May 2010 (UTC)

I agree.—Emil J. 16:06, 26 May 2010 (UTC)

Easily computed 'No' Answer to 'Yes/No' Question.

Perhaps this does not belong here but I am curious, regardless. Is there any known time complexity for determining a 'no solution exists' for a known NP time complexity problem? For example in the TSP problem if there exists no such graph, is there a polynomial time algorithm that will determine that no such graph exists? —Preceding unsigned comment added by 67.185.162.191 (talk) 06:59, 18 December 2009 (UTC)

No, there is no known algorithm for that. For starters, if you could always find out in polynomial time if the answer is "no", then you can solve the problem in polynomial time. --Robin (talk) 14:34, 18 December 2009 (UTC)

I don't think that is entirely true. There would only be polynomial time solutions for languages that had no solution. For the languages that had one or more solutions the P vs NP problem would still be open. E.g. the TSP asks for the shortest route that visits all cities not 'does a route exist that visits all cities'. Perhaps I am confused and need further clarification. Also header of this post was awkwardly phrased... —Preceding unsigned comment added by 67.160.119.23 (talk) 11:47, 20 December 2009 (UTC)

The complexity classes P and NP deal with decision problems, i.e., yes/no questions. The decision version of TSP is the following: given an edge-weighted graph G and a value s, does there exist a cycle in G that visits all nodes (cities) and has total length at most s. The answer to this question is either "yes" or "no". If you could tell if the answer is "no", you could solve the problem. — Miym (talk) 12:16, 20 December 2009 (UTC)

Ok, just to get this clear, developing a P complexity algorithm that outputs a 'yes/no' to an NP-Complete problem without giving information about the solution e.g. the TSP outputting 'yes/no' with no information regarding the graph would imply P = NP...This doesn't seem very useful and it doesn't seem like it would have the consequences mentioned in the P=NP section, as one wouldn't actually have the 'program' or 'proof' only know that it exists/doesn't exist. I appreciate anyone's continued input. —Preceding unsigned comment added by 67.160.119.23 (talk) 09:20, 21 December 2009 (UTC)

Yes, solving NP-complete decision problems in polynomial time is enough to show that P = NP, and yes, it does have the consequences mentioned in this article. For example, the page NP-equivalent shows how to solve an NP-hard optimisation problem efficiently (= finds a solution) if you have a black box procedure that solves the decision problem efficiently (= just answers yes/no). A similar trick ("self-reducibility") works for most classical NP-hard problems, including TSP. — Miym (talk) 09:55, 21 December 2009 (UTC)

- NP=P problem asks for a straightforward math formula or algorithm as termed in computer science to have NP=P to be functioned. If this is found, computer will run a lot faster and advanced computing will be possible in the future for complex goals to be reached.Personally I think this is possible, as long as NP can run back and forth with P in the process in the two rounded cycles (or just one) or NP and P are rejenuvating with each other as long as P equates the NP in different sum. —Preceding unsigned comment added by 61.222.251.182 (talk) 08:44, 21 July 2010 (UTC)

Introduction

I don't think the introduction section in this article is well constructed. For someone non versed in computational theory (like me) coming to have a basic understanding of what P=NP means, the introduction is extremely confusing. The fact that neither P nor NP are defined until much later on is an example of this problem. A well structured introduction would explain, in simple terms (at the level of an intuirive desctription as much as possible) P and NP (and the space in which they are defined), and then explain what P=NP means and implies. The examples in this section are good, but without a proper context they are just examples. Yes, I know there are links to other articles defining P and NP, but the basic explanation of these two fundamental terms should be in there to provide context. Not being a specialist in the area (by a wide margin) I will not modify the article, but I suggest someone with more knowledge on the subject makes a major revamp of this section. Herbys (talk) 04:31, 21 December 2009 (UTC)

You are right. Assume, for purposes of contradiction, that P==NP. What would you do? QED Mathiastck (talk) 16:59, 31 January 2010 (UTC)

I found the same, Herbys. In particular there's no insight into what this might mean for a layman until the 8th page of text (on this laptop). Is there some Wiki reason we shouldn't mention the importance for cryptology in the very first paragraph?

Theoretical computer science is branch of applied mathematics

I see there has been some controversy regarding listing theoretical computer science as part of applied mathematical sciences. While clearly there is divide with some editors (guy named EmilJ supposedly a mathematician in real life) arrogantly stating his opinion (theoretical computer science not part of applied mathematics) as fact while clearly some disagree. In fact, I would like to point your attention to the template from wikipedia, which lists Theoretical computer science as being part of applied mathematical sciences. It is moreover classified as such at many universities, in US and elsewhere. So, clearly wikipedia community has already had a (supposedly concensus) decision to list it in applied math template, then I dont see why this guy (EmilJ, a POV motivated insider) reverts what has already been established.

see

Dlakavi (talk) 19:58, 17 March 2010 (UTC)

In general, "applied mathematics" refers to problems on the continuous side of the continuous/discrete divide in mathematics, such as the solution to differential equations; TCS and discrete mathematics are separate. Most theoretical computer scientists are not in applied mathematics departments, or not in math departments at all: they are in computer science departments. It is much more accurate to say that TCS is a branch of computer science than it is to say that it is a branch of applied math. And quoting a wikipedia navbox that some Wikipedia editor made that repeats the same mistake is hardly evidence of anything. But I don't see the need for explaining here what theoretical computer science is: the name is more or less self-explanatory and anyone who wants to know more can click the link. Additionally, regarding your other changes, the Clay math institute does not represent the mathematical community. The community did not get together as a whole and vote for the Clay math institute to give these prizes. Rather, the Clay math institute acted independently in offering them, representing only itself. And "can solutions themselves also be find quickly?" is horrible horrible grammar. —David Eppstein (talk) 21:58, 17 March 2010 (UTC)

Grammar putdowns aside (mind your own WP:CIVIL - not all editors of this wikipedia are native english speakers!) many things this editor said are plainly not true. Discrete mathematics is as much part of modern applied mathematics as its older "continuous" parts. Graph theory and Combinatorics are as important today as say fluid dynamics. For a computer scientist there is a natural bias in this sort of questions. But fact is that whole CS departments at some universities (UIC for instance) are parts of mathematics departments. Similarly, Statistics has sometimes their own departments, sometimes is part of applied mathematics departments. Why would Computer Science be condidered in different way than Statistics. Many famous theoretical computer scientists are at mathematics departments: Michael Sipser, Peter Shor are for instance at MIT applied mathematics department (part of math department), Michael is in Theory of Computation Group which has members from both mathematics and CS departments at MIT. Moreover, Clay Mathematics institute is not some random institution, is has deep connections and foundation in mathematics community (http://www.claymath.org/about/mission.php), with top mathematics people in advisory board. Mathematics community does not mean some formal organization, it consists of real people with various degrees of influence (just like wikipedia community is), which are not always formal. And Nevanlinna prize, considered one of the top prizes in CS (mathematical aspects of it presumably), is given at ICM. Rolf Nevanlinna is primarily considered a mathematician, just for the record (so is Alan Turing who I am sure no theoretical computer scientist would disown). And these prizes were clearly given for some of the most important advances in theoretical computer science. So, argument for independence of Computer Science, especially its theoretical part, of mathematics is blatant POV to say the least. Dlakavi (talk) 13:16, 18 March 2010 (UTC)

OK, let me try this one last time. Theoretical computer science consists of many subfields, like complexity theory, computability theory, algorithms, etc. Some would agree that complexity theory can be considered a part of discrete math. Some would agree that computability theory should count as a subfield of logic/foundations. We are not saying that TCS is unrelated to math, but that TCS is not a part of applied math. I can't say it any clearer than this. --Robin (talk) 13:43, 18 March 2010 (UTC)

As clear from my post above, it is not true that discrete mathematics or Theoretical Computer science are disjoint or independent of Applied mathematics. The overlap is there, and hence your thesis is wrong. While what is branch of what can be a matter of terminology and interpretation, it is no secret that theoretical computer science has its origin in mathematics. Also, Applied mathematics is not the same thing as some particular British tradition, this is clearly POV against contributions from other nations - from Hungary (say, Erdos - who was doing a lot of discrete math; some I see suggest discrete math also has nothing to do with applied mathematics), and they are certainly important. Dlakavi (talk) 12:29, 19 March 2010 (UTC)

I would agree with the view that computer science is not a part of mathematics. Donald Knuth, perhaps the best known computer scientist, has a rather long article on this topic, titled "Computer Science and its Relation to Mathematics", where he concludes neither field is a subset of the other. As purely practical evidence, I belong to both the MAA (Mathematical Association of America) and the ACM (Association for Computing Machinery), probably the two largest professional organizations dealing with these topics. In terms of journals, papers, and all other practical artifacts of the field, computer science stands as its own subject, not a part of mathematics (whereas applied mathematics is definitely treated as a part of mathematics in general, for example). LouScheffer (talk) 00:19, 18 March 2010 (UTC)

I'm also of the opinion that "Theoretical Computer Science" is not "Applied Math". Any field of study can justifiably be defined by (1) the set of problems that it attempts to solve and (2) the methods it uses to solve them. Both of the fields in question encompass many different problems and many different tools to solve them; there's certainly some overlap between them. However, a closer look at the two fields shows some fundamental differences, especially in the methods they employ to obtain a solution.

Furthermore, having TCS listed in an AM template does not imply there was a consensus. I imagine most people in these two fields are simply apathetic about their distinction.

- Jwesley₇₈ 00:40, 18 March 2010 (UTC)

As everyone else said, TCS is not applied math. Also, please be WP:CIVIL. --Robin (talk) 00:54, 18 March 2010 (UTC)

If you all agree that Theoretical Computer Science is not part of applied mathematics, than there is no place for it on the applied mathematics template. You cant have it both ways. Dlakavi (talk) 12:32, 18 March 2010 (UTC)

So take it off the template. But then discrete math should also not be on the template. —David Eppstein (talk) 15:00, 18 March 2010 (UTC)

Regarding having it "both ways": Are you going to purge theoretical CS journals of people associating with SIAM journals. Good luck! ;) Why don't you fellows start by removing all the mathematics from the Theoretical computer science article! Kiefer.Wolfowitz (talk) 19:41, 18 March 2010 (UTC)

• Please, see Newell, Allen; Simon, H. A. (1976), "Computer Science as Empirical Inquiry: Symbols and Search", Communications of the ACM, 19, mathematics is not Empirical Inquiry!--Tim32 (talk) 18:54, 18 March 2010 (UTC)

SIAM and "applied"

Being listed on the applied mathematics template doesn't imply that theoretical CS is a part of traditional British applied mathematics, any more than the section on statistics and decision sciences implies that statistics is part of applied mathematics.

SIAM publishes

• SIAM Journal on Discrete and Algebraic Mathematics
• SIAM Journal on Computing
• SIAM Journal on Optimization

all of which are covered by the CS reviewing journal; all of these journals have significant overlap in editorial boards, author, references, with the leading CS journals. This argument could be strengthened by looking at the ISI list of journals in CS theory, but I assume you recognize that theoretical CS has a substantial overlap with applied mathematics. (IMHO, this overlap is much larger than the overlap with mathematical statistics.) SIAM cosponsors many of the main prizes in theoretical computer science (or at least prizes that prominently feature theoretical computer scientists): George Dantzig prize, the Fulkerson Prize, etc.

The Theoretical computer science article plants the CS flag on many mathematical theories: Category theory, Graph theory, number theory, mathematical logic, etc.! (Why avoid the connection to mathematics now?)

I am guessing that the previous editors are rightly concerned that Theoretical CS has much less overlap with the grand British tradish of "applied mathematics", with analytic methods (and some heuristics) applied to problems of physical science---But what about the extensive literature on formal power series and automata theory? Would you feel more comfortable if the template were relabeled Applicable Mathematics OR Industrial and Applied Mathematics? Thanks Kiefer.Wolfowitz (talk) 19:09, 18 March 2010 (UTC)

Just a quick note: Apllied mathematics is not exclusively "British", and there is no reason why a British tradition should have any more weight than say, French, German or Russian. Dlakavi (talk) 12:23, 19 March 2010 (UTC)

So there's no confusion, the question is not to what extent are TCS and Math related; they obviously are. In some ways, Computer Science (as a whole) is an "applied" branch off of Mathematics. The question here is specifically whether "Theoretical Computer Science" should be lumped into the category of "Applied Mathematics". TCS is the least "applied" of any field in CS. Many topics in TCS have no direct application. Since TCS is often not-in-any-way "applied", placing TCS within AM might be worse than placing another more applied field of CS (e.g., Artificial Intelligence) into AM. Jwesley₇₈ 20:01, 18 March 2010 (UTC)

Can we try to change the name of the template so that it is somewhat coherent and lists the topics of mathematical research that have strong ties to (empirical) science, engineering, and other concerns? I would suggest "Applicable Mathematics" or "Mathematics for Applications". Would that be better and acceptable?Kiefer.Wolfowitz (talk) 20:10, 18 March 2010 (UTC)

I changed the template's name to "Industrial and applied mathematics", which indicates the SIAM-like scope, ecompensing mathematics of computing, discrete and algebraic math, etc.Kiefer.Wolfowitz (talk) 19:25, 20 March 2010 (UTC)

My two cents is that it's absurd to say that PvNP is "one of only three problems on the list that are not in traditional pure mathematics fields". For starters, this assumes that there's a well-defined notion of "traditional pure mathematics" which is of course preposterous. Moreover, the classification of a problem in a mathematics subfield is neither static nor exclusive. Elliptic curves can reasonably considered as a topic in cryptography, but only since the 80s. It would be silly to view the AKS primality test solely as a complexity result and discard the fact that it's also a number-theoretic advance. Are complex numbers "pure math" or "applied math"? It's an absurd question. Does group theory become applied math if someone describes a rubik's cube solution in terms of commutators and orbits? Pichpich (talk) 19:13, 19 March 2010 (UTC)

Almost all topics in Math have, or will have, an application. What distinguishes "pure" and "applied" mathematics is its motivation for study. The study of Cryptography is motivated by the need for secure communications, and thus "applied". The study of Algebraic Geometry is motivated by its "beauty", and thus "pure". Furthermore, it's not the mathematical objects themselves (e.g., Complex Numbers, or Elliptic Curves) that are applied, or pure, it's the study of such objects. (The objects themselves are simply objects for study.) Of course, each field (and each researcher in that field) varies in his/her/its motivation, but some fields fall rather clearly into either "applied" or "pure". Jwesley₇₈ 19:47, 19 March 2010 (UTC)

Right, but still, I agree with Pichpich — the "not in traditional pure mathematics" line is wrong. P versus NP is a question in mathematical logic, which is definitely one of the fields of traditional pure mathematics.

That's not to say it's only part of math logic (this insistence on imposing artificial hierarchies on the field is the bulk of the problem in this discussion). But it is part of math logic, and therefore traditional pure math. --Trovatore (talk) 22:08, 19 March 2010 (UTC)

Agree with Trovatore. I would add the following subtlety. There are very few, if any, researchers in the field that actually believe that P=NP. This is important because, from a practical standpoint, a proof that P!=NP is of little value. So what if there's no polytime algorithm for SAT? We have great sat-solvers, gazillions of heuristics that perform quite well on combinatorial optimisation problems and algorithm designers don't lose sleep over the NP-completeness of their problem. The fascination with the PvNP question is not grounded in the practical implications of its resolution. In any case, my original point was simply that it's silly to try and distinguish pure/applied in such absolute terms: the vast majority of mathematicians are fascinated with the aesthetics of their field of study, whether or not they have applications in mind. Pichpich (talk) 23:11, 19 March 2010 (UTC)

I agree, the "not in traditional pure mathematics" should be removed. I was focused on a slightly different discussion that's going on here. Jwesley₇₈ 23:20, 19 March 2010 (UTC)

Applied Mathematics template

I started a discussion on the talk page for the "Applied Mathematics" template about removing Theoretical Computer Science from it. Jwesley₇₈ 17:25, 18 March 2010 (UTC)

I started moved this discussion on to Wikipedia talk:WikiProject Mathematics#Theoretical Computer Science. That page would likely be the best venue for this discussion. Jwesley₇₈ 18:12, 18 March 2010 (UTC)

Layman explanation?

The same way that a layman page now exists for the solution to the Poincaré conjecture, shouldn't there be a "layman page" describing the remaining millenium problems?

I have some backgrounds in mathematics, but not to the extent required by this page to be understood.

And ideally, a link should be made at the top of each such page stating, for instance "This page requires familiarity with (mathematics|computer science|whatever). You may find a more approachable (but less accurate) description of the problem here: <link to the layman page>"

What do you think? —Preceding unsigned comment added by 90.24.123.230 (talk) 19:26, 19 March 2010 (UTC)

With all due respect, this page is the laymen page, and is considerably more accessible than other pages related to computational complexity. If you think there's something that's unclear we'd be glad to clarify it. Forking articles by audience may or may not be a good idea, but is not generally practised on Wikipedia. Dcoetzee 05:11, 20 March 2010 (UTC)

I think you have a good point, but maybe not the one you thought. Most of the article is pretty accessible - the problem of "written for specialists" is (mostly) restricted to the sections "Formal Definition for...". The problem is that these are right near the beginning, and many readers (I suspect) will stop reading there, and miss the more easily approached text that is later. I think moving the more formal sections to the end would address this issue. I'll do this, LouScheffer (talk) 09:05, 20 March 2010 (UTC)

How about removing the formal definition altogether, and referring the reader to our articles on P, NP and NP-complete for that information? Those articles do give the formal definition in terms of Turing machines (and uniform families of boolean circuits). --Robin (talk) 13:56, 20 March 2010 (UTC)

Determinism

I dispute the apparent claim that modern computers are almost exclusively deterministic. Programming a modern multi-threaded multi-core CPU soon reveals the care required to ensure that execution is indeed deterministic. My proposed amendment mentions race condition as one consequence of getting this wrong. I'm on a mobile phone at the moment, but will add more details when my land line is fixed. Stephen B Streater (talk) 18:06, 21 March 2010 (UTC)

This has nothing to do with P versus NP problem. Do not add it here. The type of nondeterminism you discuss (in which more than one possible sequence of events can occur) is very different from the mathematical model of nondeterminism in the P vs NP problem (in which ALL possible sequences of events are selected among). —David Eppstein (talk) 18:34, 21 March 2010 (UTC)

So can I assume you are happy to take out the unsourced and incorrect claim that almost all computers as of 2010 are deterministic, which by my interpretation of your reasoning also has nothing to do with the P versus NP problem? Stephen B Streater (talk) 18:46, 21 March 2010 (UTC)

It's certainly not true that almost all computers these days are sequential. —David Eppstein (talk) 18:51, 21 March 2010 (UTC)

I agree that there is some confusion caused by non-deterministic having a different meaning in this area to not deterministic, but deterministic is actually described in this section as meaning that the output can be derived from the input - which is not the case in a multi-CPU computer or a typical multi-threaded program. Stephen B Streater (talk) 18:58, 21 March 2010 (UTC)

Well, he took out the false claim; don't know if you noticed. --Trovatore (talk) 19:03, 21 March 2010 (UTC)

I hadn' noticed yet - my 24Mb/s broadband isn't working, so I'm on a dodgy 9.6kb/s mobile phone browser :-( Stephen B Streater (talk) 20:03, 21 March 2010 (UTC)

Multithreaded programs are typically written to behave deterministically - that is, to produce an expected fixed output in response to each possible input. The very challenge of multithreading comes from achieving deterministic computation using an unpredictable schedule. I think some form of the original statement remains true, since programs which randomly do one thing or another (which complexity theory would refer to as probabilistic) are not terribly useful in practice, except when it's used in a controlled manner as in random algorithms. Dcoetzee 06:01, 13 April 2010 (UTC)

You may be interested in the success of Monte Carlo methods in computer Go. Stephen B Streater (talk) 06:58, 13 April 2010 (UTC)

True... I think what I'm getting at is that in random algorithms the randomness typically comes from an explicit random source, rather than the unpredictability of concurrent thread schedules accessing shared memory. Although when I stop to think about it I've seen exceptions to this (most obviously, work-stealing queues). But I digress. :-) Dcoetzee 07:24, 13 April 2010 (UTC)

Rampant complexity theory bias

It is very common for people who work in complexity theory to use the words efficient and polynomial time interchangeably, and indeed you will see the word "efficient" formally defined to mean polynomial time. In the real world these concepts are sometime related, especially for introductory-level algorithms taught at universities, but often they are not. The very misleading equivocation of these two concepts has been a tremendous PR boon for complexity theory. Someone with sufficient background in computer science will or at least ought to understand this while reading this article, but everyone else will not understand this -- and indeed it seems that many who have been writing this article do not understand it, or have been embedded in a culture of equivocating efficient and polynomial for so long that they are not able to write in a non-misleading manner any more. The result is that this article reads as a PR-piece for research in complexity theory. That's not to say that complexity theory isn't valuable and important, it's to say that a Wikipedia article should not be a PR piece. That is true even though the PR is very much verifiable as this article reads exactly as complexity researchers often present their work, so those presentations can be easily cited. This is equivalent to citing commercials for a vacuum cleaner to establish that it is "best in the world" and "the best price you will ever find."

In particular, absolutely nothing of direct value to actually computing things can be derived from knowing that NP=P or that NP!=P. What matters for actually computing things is *efficiency* for the inputs you care about, and that is independent of whether NP=P. The practical consequences of proving that NP != P are of the same kind as of those for Galois' proof that you cannot square the circle using compass and ruler. It is useful in that it allows people to know that they should no longer spend their time looking for a method to do so, since it cannot be done -- that is a very important practical thing to know for people doing research. Outside of that it is a tremendous advance in human understanding. The practical consequences other than these are absolutely nothing. I know that a statement to that effect is tucked away in a little corner of this article. Still, reading this article in its entirety, the meaning of NP=P is presented in a way that vastly overstates its practical importance.

Someone might prove that NP=P by constructing an algorithm that efficiently and in polynomial times solves an important NP-hard problem. It is without a doubt that that would have tremendous practical consequences of the type presented in this article. However, what would create those consequences would be that the algorithm is efficient. It is irrelevant that it is polynomial in the complexity theory sense. Someone might tomorrow come up with a truly efficient algorithm to solve an important NP-hard problem without that algorithm being polynomial, and that would have exactly the same remarkable consequences. Efficient and polynomial time are not the same thing.

130.225.0.251 (talk) 20:14, 9 April 2010 (UTC)

Interesting. But I think people may find it hard to find optimal solutions to NP problems in P!=NP for large problem size. That doesn't mean they will find it easy if P=NP, of course, as the polynomials might also grow quite quickly, but exponentials grow faster than polynomials eventually - and with modern computers, that could be quite soon. Stephen B Streater (talk) 20:41, 9 April 2010 (UTC)

There are two constants in the definition of asymptotic complexity. One is the coefficient, the other is the size of input from which that complexity kicks in. It really does not matter for any practical concern what the complexity is for sizes beyond, say, 10^100000. Yet a proof of P != NP would concern such sizes, which is a understatement by a lot since asymptotic complexity is about what happens for arbitrarily large such constants, so even 10^100000 or any fixed constant at all is too small to say what it is that a proof of P != NP would concern. Asymptotic complexity is about what happens at infinity and practical matters don't happen at infinity. 93.182.137.109 (talk) 22:33, 9 April 2010 (UTC)

P=NP won't make problems instantly soluable, but P!=NP will show they are insoluable in practice for, say sizes of 100000 (which are quite manageable questions to ask on a modern computer), where the soloution requires 10^100000 steps. A lot of banks will be sleeping a lot more soundly if they knew that was the case. Stephen B Streater (talk) 23:10, 9 April 2010 (UTC)

This is precisely the kind of misunderstanding that the language of complexity theory creates. The number 100000 is not infinity, and so a proof that P != NP says absolutely nothing about it. It does not say anything about any particular size of input. If P != NP, then for each particular algorithm and each particular polynomial p, there is some constant c such that for inputs larger than c, the runtime grows faster than p does. That P != NP says absolutely nothing about what c will be for any given algorithm and given polynomial. So that P != NP says nothing like what you state here, but it is perfectly understandable why you would think something like this given the way asymptotic complexity is often presented. Cryptography depends on specific, given instances being hard to solve, while complexity theory is about the worst case instances at infinity. These are very different things, and so showing that P != NP does nothing to prove cryptographic systems secure.

But it seems that in practice there are no exponential problems which can be solved with n=100000, even though it is not infinity. Stephen B Streater (talk) 07:15, 10 April 2010 (UTC)

That's not true, but I don't see a reason to explain since that is not related to the issue at hand. 93.182.138.109 (talk) 20:34, 10 April 2010 (UTC)

I understand your point, but the lead does make it clear that the words "easy", "difficult" and "quickly" are to be taken with a grain of salt, which is why they are enclosed in quotes. Then the next few sections just describe the problem. Then there are the sections on philosophical musings about the problem, which you might find misleading. But they do state that it's possible that P = NP, but the algorithm is not practical, or the proof is non-constructive. Finally, P versus NP is the biggest open problem in complexity theory, so it is natural that the page makes complexity theory sound interesting. The page on Goldbach's conjecture does make number theory sound very interesting.

It might be easier if you WP:BE BOLD and edit the parts that you find misleading. If it gets reverted, then those sentences can be debated. --Robin (talk) 23:26, 9 April 2010 (UTC)

I have no objection to complexity theory sounding interesting. It is a fascinating subject that is one of the great achievements of theoretical computer science. I would like complexity theory to be appreciated for its rightful strengths rather than through misinformation. In that vein, the quote by Scott Aaronson of MIT is crazy. Offering counter quotes saying that perhaps P does equal NP is not enough. The article reads as though what Scott Aaronson writes is true and reasonable. But P = NP has nothing like the kind of consequences he brings up. As the article is now, it stands unopposed that if P = NP, then everyone who can appreciate Mozart will be a Mozart. Now as someone with a background in computer science I can interpret that in a way so that it makes some sort of tenuous sense, but the sense that it makes is far removed from the words used. The majority of people reading this quote will be grossly misled, even if they correctly assume that Aaronson is going for some sort of metaphor instead of literal truth.

It's true that in some places some words like quickly are in quotes, but there is not an effort to say what those quotes mean. I read them as meaning that the terms are imprecise, not that they are misleading.

I will see if there is something I can edit, but I think it will be hard for me to do so with a neutral point of view. 90.185.194.132 (talk) 00:25, 10 April 2010 (UTC)

One example of an algorithm which is in P, but not "efficient", is the AKS primality test, which runs in time O(n^6+ε). Yes, this is polynomial, but very inefficient. It's essentially unusable for large primes; it would only be used if you needed the utmost assurance that the number is indeed prime. Justin W Smith ^talk/_stalk 04:31, 10 April 2010 (UTC)

I agree slightly about the bias issue. The quotes about Mozart are merely illustrative. WP guidelines say articles should be written with a non-expert reader in mind, and these quotes are as close as many non-mathematicians will get to understanding the issues. Anyone who already knows anything about the area will know that many polynomial probelms are intractable, and also that NP is much easier than non-computable. I think Mr/Ms IP should put your cards on the table and make some edits, preferably without making the article less enjoyable to passing visitors who hear abojut the prize on offer, for example. Stephen B Streater (talk) 23:38, 10 April 2010 (UTC)

OK, I had a go at the introduction. 90.185.194.132 (talk) 14:10, 11 April 2010 (UTC)

Almost every (natural, not-contrived) problem in P has a known complexity no greater than O(n^3), often even near-linear. Problems in P, like AKS, with a time complexity not known to be any better than O(n^6) are the "exception rather than the rule". Typically, problems in P are efficiently solvable, e.g., sorting in O(n log(n)). Thus, terms like "efficiently solvable" are often appropriate for such problems. This reminds me of a discussion I had earlier with David on Talk:Graph isomorphism#Complexity, in which I mistakenly thought NP-complete problems problems were the "exceptional" problems. Instead, NP problems (not known to be in P) that, after inspection, are not shown to be NP-complete tend to be the "exception"; Most NP-but-not-in-P problems are NP-complete. It appears that problems in P tend to be very easy, and outside of P tend to be very hard. I doubt it's just a coincidence that these "exceptional" problems on both ends involve primes/factorization. Justin W Smith ^talk/_stalk 04:56, 11 April 2010 (UTC)

Yes, problems that are proven to be NP-complete tend to be harder to solve in practice than those that are proven to be in P. There are lots of exceptions to this. E.g. many results of the form "polynomial time for fixed k", where k is some parameter, is for algorithms that have running times exponential in k. Choose k moderately high and you will usually have a very impractical polynomial algorithm that is beaten by quite practical exponential algorithms for any conceivably practical input size. ML type system inference is another example where an NP-complete problem is routinely solved on desktop computers for huge inputs in little time. I've never made a habit of collecting such examples, but they are prevalent enough even without looking for them.

The worth of complexity theory is not in predicting whether an algorithm will be fast in practice. The practical worth of complexity theory is to quickly spot claims that are likely flawed (to spot your own error or to spot a crackpot) and to guide algorithms researchers in what kind of algorithm technique will likely succeed for a given problem. 90.185.194.132 (talk) 13:12, 11 April 2010 (UTC)

I gave the introduction a go, but another editor seems insistent on transforming what I wrote into something that is even more misleading than how the introduction started out. I don't really care enough to spend more time on keeping Wikipedia honest, so if no other editor cares either, that is the way it will be. 90.185.194.132 (talk) 17:42, 12 April 2010 (UTC)

I'm not sure what is "misleading" or "dishonest". I made the editorialization of the terminology a footnote, since I though it would be more consistent and encyclopedic. Justin W Smith ^talk/_stalk 18:09, 12 April 2010 (UTC)

Section: "Efficiency and tractability"

I created a new section to discuss the terms "efficiency" and "tractability", which have a meaning that differs from what one might expect. (I suspect the section will be removed by another editor.) Feel free to discuss this section here. Justin W Smith ^talk/_stalk 00:54, 10 April 2010 (UTC)

As noted by another editor above, "efficient" is used several places in the article in a way that is, at best, unclear. Would an "editorial"-type comment about the usage of the term "efficient" be appropriate as a footnote? Justin W Smith ^talk/_stalk 04:18, 10 April 2010 (UTC)

As far as I can tell all uses of "efficient" in the article are used in their colloquial sense, of something that runs fast enough to be practical. I don't see the evidence that they are used in some made-up technical sense that needs to be explained. In particular, in section "Consequences of proof", the existence of practical algorithms for NP-complete problems is not treated as a necessary consequence of P=NP, but as something that might also be true. So I don't see what you're so worked up about. —David Eppstein (talk) 04:51, 10 April 2010 (UTC)

You're right. After reading over the relevant sections again, the article does seem quite careful about its use of these colloquial terms; the word "efficient" is only used with its usual meaning. The section Does P mean "easy"? further eliminates concern about misleading the reader about the implications of a problem being in one class or another. Justin W Smith ^talk/_stalk 05:08, 10 April 2010 (UTC)

This has been a recurring issue in this article, since the P versus NP problem is a magnet for attention, but really the practicality of P algorithms is only a related issue with an older history and wider implications than just the consequences of P=NP. This is why most of this content was moved out to the article on Cobham's thesis, which could use some of the attention given to this article's treatment of the issue. Dcoetzee 05:58, 13 April 2010 (UTC)

What is this?

An IP user (76.168.249.213) added the following to first section of this talk page (i.e,. under "New section to add"):

\Delta_2^{\rm P} = {\rm P^{NP is the class of problems solvable in polynomial time with an oracle for some NP-complete problem.

I reverted this and a couple other of his changes to the article b/c they looked suspicious to me, and I couldn't verify them from any source. Justin W Smith ^talk/_stalk 23:57, 13 April 2010 (UTC)

This is of course perfectly standard notation for parts of the polynomial hierarchy, but it's irrelevant here. Note that this IP user is doing it periodically (i.e., inserts irrelevant though mostly correct complexity-theoretic material into NP-related articles).—Emil J. 10:04, 14 April 2010 (UTC)

Ok. I found the complexity class listed here. I had looked in Arora & Barak and saw no mention of the class. (Obviously, it's a beginning textbook and does not have an exhaustive list of classes. But, if it was relevant to this article, I'm sure it would be covered.) I still don't understand the third algorithm, that the IP listed. It begins with the line: "The upgrade patch may now be installed by the M-frames installer service apropos the program to be". Say what? :-) Justin W Smith ^talk/_stalk 13:14, 14 April 2010 (UTC)

Well, the algorithm itself is easy enough to understand: it only consists of comments, hence it does not actually do anything. Where the rubbish is taken from and what is it supposed to demonstrate is beyond my comprehension.—Emil J. 14:25, 14 April 2010 (UTC)

Featured?

I could have sworn this article was featured in the past. I'm not really competent to work on this myself, but it really should be a featured article. mkehrt (talk) 00:12, 30 April 2010 (UTC)

Honestly I think it's not close to meeting those standards, although it is one of the best treatments of the subject I've seen. A good article might be a better place to start. Dcoetzee 02:43, 30 April 2010 (UTC)

Yes, definitely not close to FA status. Not GA status either, but that's more achievable. I have no idea how to go about reaching that quality, although I'm willing to help if anyone has any ideas. --Robin (talk) 02:46, 30 April 2010 (UTC)

Edit request from Luke18:2-8, 3 June 2010

{{editsemiprotected}}

Changed protection level of P versus NP problem: Excessive censorship ([edit=autoconfirmed] (expires 05:22, 3 July 2010 (UTC)) [move=sysop] (indefinite))) Generic NAMESPACE:P versus NP problem PAGE NAME (edit | talk | history | links | watch | logs) NAMESPACE talk:P versus NP problem PAGE NAME (edit | nAMESPACE | history | links | watch | logs) Luke18:2-8 (talk) 11:24, 3 June 2010 (UTC)

The place to request unprotection is WP:RPP. Algebraist 15:14, 3 June 2010 (UTC)

Consequences of proof

The statement "Firstly, it would change geopolitics, particularly the economy, national security, modern warfare, and intelligence. P being proven to equal NP means that no data encryption method is unbreakable, no matter how sophisticated, given enough computational resources and time." is incorrect on several grounds.

First, P == NP might not have any practical consequences at all (if proof is non-constructive, or the polynomial order is too high). For example, the method shown in "primes is in P" is not used in practice, to my knowledge.

Second, even if P==NP and an efficient method is found, several types of encryption remain safe:

• One time pads, since any answer is as likely as any other. P==NP cannot help with this.
• Quantum encryption, which depends on QM and not on computation.

Third, the statement "no data encryption method is unbreakable, no matter how sophisticated, given enough computational resources and time" is true whether P==NP or not.

There is no need to exaggerate - "stunning practical consequences" is already enough. LouScheffer (talk) 15:05, 19 May 2010 (UTC)

• A lay reader would not infer security implications from "stunning practical consequences", as practicality and security aren't even distantly semantically related.
• Even if there are new cryptographic techniques which negate any impact of an efficient method being found, existing data security strategies won't abandon the old and insecure techniques overnight. Many of these encryption techniques are hardwired into chips in essential equipment, such as televisions, cars, hospital equipment, and ATMs. Such a sudden, enforced exodus would break many information systems.
• There are too many papers that discusses the relationship between the P versus NP problem and cryptography for the issue of cryptography being entirely left out of the P versus NP article. Stephen Cook's manuscript which is cited a couple times in this article is one of them (see page 9). It seems biased, even if the body of literature is really stretching the issue, that the topic is ignored altogether. The history of this mathematical area is significant, and worth knowing.
• With any extremely powerful tool--as another example, fire--comprehensive reference sources should not, through omission, imply that no one has thought they might be dangerous, especially when many people have. It's also true that scientists and mathematicians (and everyone else, for that matter) are wrong all the time. Perhaps P versus NP won't have any negative consequences, but to not even consider them in something considered to be so powerful is highly foolish. In an encyclopedia, to not even mention the discussion in the literature is negligent.

67.240.173.68 (talk) 16:29, 19 May 2010 (UTC) Joe

It's very reasonable to mention that a constructive and efficient solution to certain NP-complete problems would break many existing cryptosystems. But that's about as far as you can go without exaggerating. LouScheffer (talk) 18:13, 19 May 2010 (UTC)

By definition, an efficient solution to any NP-complete problem is an efficient solution to every NP-complete problem. However, while finding a polynomial solution to an NP-complete problem would prove (by example) that P == NP, the converse is not necessarily true. More importantly, though, the most commonly used encryption protocols are not based on NP-complete problems, but on integer factorization and discrete logarithms. I say protocols and not algorithms, because these systems usually combine multiple algorithms: asymmetric-key algorithms based on factorization or logarithms are used to authenticate the parties and exchange randomly generated session keys, while the data itself is encrypted with symmetric-key algorithms using the aforementioned session keys. DES (talk) 11:42, 9 August 2010 (UTC)

That's "by definition" only in the technical sense that equates efficient with polynomial time. On the face of it it's not impossible that you could find a practical solution to some problem X that's formally NP-complete, but such that the reductions of the problems we actually want to know about to X, though polynomial time, are not practical. --Trovatore (talk) 17:50, 9 August 2010 (UTC)

Additional of a practical example

I suggest you add the following practical explanation of the problem by the Clay institute itself: http://www.claymath.org/millennium/P_vs_NP/

(attributing the copyright, of course)

The explanation does make things extremely more simple and clarifies the concept for non-mathematicians which is definitely a subgroup of people that this site is targeting. —Preceding unsigned comment added by Lyzazel (talk • contribs) 20:20, 19 June 2010 (UTC)

Attributing the text does not allow us to copy it wholesale. Fair use only extends to short quotations. See Wikipedia:Quotations#Fair use. Dcoetzee 09:12, 8 August 2010 (UTC)

biography

Someone has written a biography Vinay Deolalikar, sigh. I have suggested on its talk page that it be afd'd. 75.62.4.94 (talk) 16:20, 9 August 2010 (UTC)

AfD is now in progress. 75.62.4.94 (talk) 17:40, 9 August 2010 (UTC)

P must be equal to NP due to ontology

I need to complain that two particularly important concepts are not given due representation in the P versus N problem article.

1., If P not equal NP, then God cannot exist.

(P=!NP would allow easily creating a problem which God himself cannot solve, making omnipotence impossible. Science is not allowed to prove/disprove the exitance of God per definition, thus P must be equal to NP, where even a non-constructive proof would allow for a God.)

2., If P != NP, that means information can be effectively destroyed by encrypting it, killing the encrypter and spending more time than the available lifetime of the Universe to try regain the info from the encrypted archive.

However, we know from black hole physics that information cannot be destroyed. If things fall into the event horizon, their info content is radiated away via a not fully random electron-positron pair generation outside the event horizon. See the works of Prof. Stephen Hawking. If information could be destroyed, beings could destroy the Universe by depriving it of information, so its material would lose structure. This does not happen, therefore information cannot be destroyed, therefore P=NP is necessary. 84.21.2.137 (talk) 09:41, 9 August 2010 (UTC)

I don't believe in your god (or any other), but claiming that P =/= NP somehow proves or disproves the existence of a supernatural being is just silly. NP problems are not unsolvable, they just take a very long time to solve by conventional means. It may or may not be possible to solve them very quickly using quantum computers, and wouldn't an all-knowing god, well, just know the answer? As for your second claim, it is based on several incorrect premises: firstly, neither encryption nor decryption are NP-complete, although key recovery can be, depending on the algorithm; secondly, encryption does not destroy information, it just transforms it; and finally, information can be destroyed. In fact, the second law of thermodynamics says that information is being destroyed all the time, and suggests that we are headed toward a future (albeit a very distant future) in which no information exists at all. DES (talk) 10:02, 9 August 2010 (UTC)

>encryption does not destroy information, it just transforms it

Really strong encryption takes meaningful input and produces a garbage-looking output stream that simply cannot be distinguished from pure noise without having the decipher key at hand. If the cipher key is lost/destroyed, the crypto is truly strong and P does not equal NP, then there is no possibility to prove (before the Universe burns out) that an allegedly "crypto" data stream contains hidden information rather than pure noise. This means information was destroyed, because no-one can prove that it still exists! However, if P=NP, then you can guaranteed retrieve the plaintext info or determine that it is indeed just noise, and with a bounded amount of effort, hopefully in a time less than the remaining lifespan of the Universe. 91.82.168.184 (talk) 21:13, 10 August 2010 (UTC)

Plus, your description of Hawking radiation is not accurate. Information is not retained via Hawking radiation. Rather, the information is retained on the surface of the event horizon (shown by Susskind). As for the first reply, entropy is not the destruction of information. Information /can/ neither be created nor destroyed, per the laws of thermodynamics. Anyway, if there were a mathematical theorem that were to prove the non-existence of God, I would think it would be Godel's Incompleteness Theorem. Prothonotar (talk) 19:06, 9 August 2010 (UTC)

Hmm, I don't see anything about conservation of information in the laws of thermodynamics, but I'm a CS guy, not a theoretical physics guy, so my understanding of this may be tainted by our use of the term “entropy” in a different sense. However, say you encode information by alternately heating and cooling one-inch sections of a steel wire. Let's ignore dissipation to the environment; over time, the heat will spread evenly throughout the wire, per the zeroth law of thermodynamics, and the information will be lost. Assuming you are correct, where is the flaw in my example? DES (talk) 22:45, 9 August 2010 (UTC)

Solved by Deolalikar?

Looks like Vinay Deolalikar (here is his page at the hp webstite) has solved the issue... He came to the conclusion that P is not equal to NP

Preliminary details here.

(posting for some people of goodwill to update the article...)

Paolo (not registered yet, sorry) —Preceding unsigned comment added by 151.99.187.181 (talk) 15:10, 9 August 2010 (UTC)

Please see the "potential solution" section further up. Based on current discussion at RJ Lipton's blog, the "proof" appears to have some gaps right now. 75.62.4.94 (talk) 15:25, 9 August 2010 (UTC)

Does that make his attempt non-notable? Why not mention it?--88.74.222.13 (talk) 17:22, 9 August 2010 (UTC)

Notability is established by documentation in reliable sources. Topics are presumed non-notable until documented as notable, not the other way around. Right now there are (as far as I can tell) zero recognized experts saying (even informally) that they think the proof is correct. If any of them do, I'd reconsider. 75.62.4.94 (talk) 17:40, 9 August 2010 (UTC)

This proof has been quite pushed by some blogs ([1]) and the press seems to take notice too (for example [2]) According to [3], 'Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.”' --rtc (talk) 18:36, 9 August 2010 (UTC)

"Serious attempt" just means it's not by some crank, not that it's a correct proof. Neither Cook, Lipton, nor anyone else in the field has (AFAIK) said they think the proof is correct. If someone does (as happened with Perelman), then it gets more interesting. Right now this situation is a yawner. 75.62.4.94 (talk) 18:41, 9 August 2010 (UTC)

It's not a criterion that it has to be correct. Notability is enough, and this solution attempt has become notable. --rtc (talk) 20:51, 9 August 2010 (UTC)

I'd say noncommital blog posts and a random popular press mention don't establish notability for a purported theoretical result like this. A write-up in a CS journal would be more promising, or favorable posts from the research bloggers (the latter are not supposed to count either, but I'm not that big a policy zealot, I just want to do what makes sense, and the current situation does not qualify). I'd even be satisfied (as mentioned earlier) if the claim holds up for 1 week without being refuted. We could take it out if it were refuted later. 75.62.4.94 (talk) 21:16, 9 August 2010 (UTC)

Why? Regardless of whether it's a valid or an invalid proof, it has already had some impact. It's notable. And even if the validity is challenged next week, it is still notable. Wikipedia is not supposed to describe only valid proofs and true ideas. All the experts who had a look at the paper acknowledged that it contains new ideas that have merit even if the overall proof should turn out to be invalid. --rtc (talk) 21:50, 9 August 2010 (UTC)

Well, Scott Aaronson said something like that; nobody else did as far as I've noticed. Of course every published research paper should contain a new idea that has merit, otherwise why publish it? New idea != notability. Something like Tao's remarks about Perelman's Poincaré conjecture paper p.2 top would carry more weight, but only after the paper had been circulating for a while, much longer than 1 day. In short, this thing is way premature. Wikipedia is not a crystal ball or a newspaper. 75.62.4.94 (talk) 22:51, 9 August 2010 (UTC)

As I mentioned above, I think this proof is roughly comparable in terms of its seriousness and the reputability of its author to the proof of P=NP by Ted Swart in the 1980s. If it's mentioned, both should be mentioned as "notable proof attempts" - otherwise both should be omitted. Whether we document notable proof attempts is an editorial decision. Dcoetzee 02:11, 10 August 2010 (UTC)

I'm somewhat familiar with the Ted Swart saga and I agree that the comparison is reasonable. I don't think either attempt should be mentioned explicitly in the article. I'd prefer to just mention Gerhard Woeginger's page (currently in the extlink section) as a list of proposed solutions of varying quality that have not gained general acceptance from the research community. There is a citation along those lines in the RH article and we can do something similar. 75.62.4.94 (talk) 06:52, 10 August 2010 (UTC)

FWIW Richard Lipton wrote a good blog post a while back [4] that among other things described a failed attempt by Edward Nelson in the 1990's to prove P!=NP. 75.62.4.94 (talk) 08:05, 10 August 2010 (UTC)

I would tentatively support a "notable proof attempts" section. I think that there is enough information on previous attempts, and that this should be useful perspective for our readers. But I would advocate delaying as long as reasonably possible on the Deolalikar proof attempt: we just don't know that much about it yet. CRGreathouse (t | c) 12:48, 10 August 2010 (UTC)

I don't think there have been any really notable attempts in the past. This current one has gotten more attention than earlier ones because of the internet buzz machine that didn't exist in the 1990's etc. The current one seems to have been withdrawn from the author's web site, but if it returns I'm coming around to the idea that we should mention it, because of the amount of attention it's getting. I still support deleting the biographical article about the author or redirecting it to here. I don't think it's doing the person any good and in absence of info to the contrary I'm going to treat it as an involuntary biography (one that the subject would opt out of if he could). 75.62.4.94 (talk) 18:54, 10 August 2010 (UTC)

Interesting. I *do* think there have been notable attempts, though I'm not sure that this recent one is an example of one. CRGreathouse (t | c) 23:43, 10 August 2010 (UTC)

Let's compare the situation with Alfred Kempe's erroneous proof of the 4-color theorem that was accepted as correct for decades. That was really very famous and actually significant, and it was around 100 years ago so there's been plenty of time for historical documentation to develop. Yet we only have about 2 sentences about it, and that really seems like enough. 75.62.4.94 (talk) 03:05, 11 August 2010 (UTC)

Why restrict to computer solutions?

I've been copyediting some of the text. Not sure what to do with this sentence, Informally, it asks whether every problem with a yes-or-no answer whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.. Is it important to the core of the P v NP problem that a computer be involved? Would it be correct to rewrite the sentence as, Informally, it asks whether every problem with a yes-or-no answer whose solution can be efficiently checked can also be efficiently solved? -- RoySmith (talk) 16:13, 10 August 2010 (UTC)

The formal definition of the relevant complexity classes involves the number of steps a Turing machine (a theoretical model of a computer) would require to resolve a problem, so for formal consideration it is important. Even for the lead, where we should have an informal introduction, I think that mentioning the involvement of a computer (or other algorithm model) is useful to make it clear what's being reasoned about here - to avoid having readers come up with the false "insight" that they can simplify things by, e.g., "just knowing" the result of some basic math. That, in turn, is useful to the discussion of why relativizing proofs can't work. Please do continue banging on the lead to get it into shape, but I think we can't avoid introducing "on a computer" there. It is at least simpler than having a lengthy digression into formal models of computation at the top of the article. — Gavia immer (talk) 16:29, 10 August 2010 (UTC)

Unless one says something about the methods which can be used to solve the problem, then someone could say "... and then one asks an oracle (or God) for the answer and verifies it.". JRSpriggs (talk) 17:08, 10 August 2010 (UTC)

I think most of the recent edits to the lead have been ok, but the current version[5] has been oversimplified a little bit too much. I'm also thinking of trying to write a nontechnical overview, changing the subset-sum example to primality testing (as a problem once thought intractable but later shown otherwise) and travelling salesman (the archetypal NP-hard problem), before talking about nondeterministic machines and suchlike. The idea is that it's sometimes possible (e.g. in primality testing) to get around the apparent need for brute force searches by clever means; the P-vs-NP problem asks whether that's always possible, and is of intense interest for many theoretical and practical reasons. I'd also like to spend a bit of space describing Impagliazzo's "Five worlds" scenarios. While that paper doesn't get all that much attention in the literature, I think its points are generally accepted and so it's ok to use it for expository purposes. Any thoughts? 75.62.4.94 (talk) 18:46, 10 August 2010 (UTC)

In what way is it oversimplified? I'm not trying to pushback on your comment, just to understand it better. This is a highly technical topic, and there is a tendency for articles about such topics to become impenetrable to non-experts. I think the early part of the article should try to explain what this is all about in a way that an educated lay person could come away with some understanding. If that means over-simplifying, I think that's OK. There's plenty of space left in the rest of the article to dig into the details with greater rigor.

I see several key concepts here. One (hinted at by the explanation of "quick") is the idea of algorithmic complexity. The very concept of "a problem being hard to solve" is interpreted differently by computer scientists and lay people. You might think that conducting a census of the US population is a hard problem, but a computer scientist would shrug it off as, "Feh, that's O(n). Easy". So, we need to impart some flavor of that.

Next, the concept that there are "classes of problems" is likely to be an alien concept. The idea that counting the number of fish in your aquarium and adding up the change in your pocket are somehow "just as hard" as each other takes some explaining. Or that sorting a bridge hand is "harder" than counting how many cards remain in an 8-deck card shoe.

Next, you have to explain the idea that verifying that an answer is correct is a different problem from coming up with the answer in the first place. And, then, why anybody cares to compare the relative difficulties of these.

Add to that the unfamiliar terminology used in the field, and figure out a way to explain all that so that somebody who doesn't have a degree in higher math. And do it in a short enough hunk of prose that they don't zone off before they reach the end of the second paragraph. If you can find a way to do that without "oversimplifying", my hat's off to you. -- RoySmith (talk) 19:22, 10 August 2010 (UTC)

I don't think the article can go any farther than it does without providing an example, because there's no way to really understand what a certificate is without an example of a certificate. I also think that the first example in the article had better be one of the simple arithmetic problems (subset sum or knapsack, and subset sum is slightly easier to parse), because that's all the math we can afford to assume a reader has. If we use an example like SAT or the graph problems, they will fail to understand it and the "understand what you're reading" switch in their brain will permanently turn to "no", preventing them from understanding the rest of the article. I think that even the traveling salesman problem is too complicated for the first example, if we can avoid using it. — Gavia immer (talk) 22:56, 10 August 2010 (UTC)

In the nontechnical overview we'd describe TSP in everyday terms of a salesman visiting cities. No graphs. Everybody understands this. That's why it's an archetype after all. 75.62.4.94 (talk) 01:03, 11 August 2010 (UTC)

I think the intro has become a bit oversimplified since it has to clearly state P vs NP is about computational problems, not "is there any person in the world who can juggle bowling balls with their feet" (a yes-or-no question whose answer can easily be verified by exhibiting such a person, but otherwise not solved except by brute force search, a situation Baker Gill and Solovay anticipated with their proof about oracle separations). One clearly does not need a mathematics degree to understand the problem (including a technical level with the relevant terminology), since it is taught in undergraduate CS classes, by definition to people with no degrees. I think we are ok if the non-technical intro assumes reasonable scientific literacy, then we have a more technical description at the undergraduate CS level, then some hand-wavy discussion of the current state of research knowledge, with appropriate citations to the actual references and wikilinks to more technical articles. I'd like to restore the wording describing P/NP as a problem in TCS and logic. CS is a wide area including topics like programming language design. Even TCS is rather wide, since it includes things like computability theory, algorithm construction (of algorithms for particular problems), etc. Complexity theory (the part concerned about proving lower bounds and dealing with concrete complexity classes) is an area within TCS that is really rather specialized, but that is where the P vs NP problem comes from. 75.62.4.94 (talk) 23:59, 10 August 2010 (UTC)

Compare the following two first sentences (roughly, the one that's there now, and the one that used to be there):

The P versus NP problem is a major unsolved problem in computer science.

The P versus NP problem is a major unsolved problem in theoretical computer science and mathematical logic.

Is the second one more accurate? Probably. But, the first one is certainly not wrong. Now, put yourself into the shoes of somebody who just heard about this on slashdot or maybe the science column in the newspaper, or maybe some people talking about it at lunch. Your math background is whatever you remember from high school or perhaps college. You probably did some proofs in geometry class, a long time ago. Maybe you can even still work some differential calculus problems. Maybe you're even pretty good at hacking out some Perl code. You came here to figure just what the heck this P != NP stuff is all about. Will the second sentence help you get your head around it any better? I don't think so. -- RoySmith (talk) 00:25, 11 August 2010 (UTC)

I like the second sentence better. The version in the article used wikilinks that explain the named subject areas if you click on them. I also think the second sentence also sets an appropriate tone for the article. It is perfectly accessible for someone who reads slashdot or a science column. 75.62.4.94 (talk) 01:00, 11 August 2010 (UTC)

Potential Solution

A proof to the P vs NP problem written by Vinay Deolalikar (HP Labs) is currently circulating the internet, awaiting confirmation as he released it on the 6th of August. Is this worth inclusion in the article at this point? —Preceding unsigned comment added by 24.81.111.60 (talk) 08:05, 8 August 2010 (UTC)

• Absolutely not. — Arthur Rubin (talk) 08:58, 8 August 2010 (UTC)

  Why not? It's notable insofar as it's a fresh potential proof, making news, and the author is from HP Labs. Are we against including notable solutions to problems? 69.165.131.200 (talk) 22:33, 8 August 2010 (UTC)

• Deolalikar's result is that "P ≠ NP ∩ co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)

  I would have expected more from a CS grad student at Berkeley. Next time, do your homework. http://www.scribd.com/doc/35539144/pnp12pt Tkircher (talk) 23:14, 8 August 2010 (UTC)

  You know, you could have said that in a WP:NICE way. Try being WP:CIVIL. It doesn't hurt. --Robin (talk) 02:26, 9 August 2010 (UTC)

  Considering nobody here provided a specific citation, you can't really blame me for reading the wrong paper. I was referring to this result. Dcoetzee 01:48, 10 August 2010 (UTC)

• For a claim like this, we should wait until either it is accepted by some level of peer review (FOCS or STOC would do, it doesn't have to be a journal) or some recognized experts on the subject have expressed their confidence in its correctness. Purported solutions to the P vs NP problem appear every week and Deolalikar's position as a professional computer scientist gives this one a little more standing than most, but not so much that we should link to it yet. —David Eppstein (talk) 01:03, 9 August 2010 (UTC)
• I would tend to say "no" as well, at least until the proof has been peer-reviewed. It's true that this claimed proof has gotten some attention, but until it's been looked over there's no way to tell if it has a problem like Wiles's proof of Fermat's Last Theorem hiding somewhere in it. If it is a legitimate proof, there will be an unambiguous announcement of this at some point. For now, it's just a claimed proof with a lot of attention. — Gavia immer (talk) 01:12, 9 August 2010 (UTC)
• Do not include. There are two possible outcomes. One is that the proof will be disproven, in which case it's not worth mentioning. The other is that it will eventually be accepted, in which case it will obviously result in a major re-write of this article. But, we won't know which for a while. This is an encyclopedia, not a newspaper. We don't need to worry about getting scooped by somebody who gets to print faster than we do. -- RoySmith (talk) 01:53, 9 August 2010 (UTC)
• No, for now. At the very least a few experts in the field should confirm that the proof is correct. --Robin (talk) 02:26, 9 August 2010 (UTC)
• I agree with Robin and the rest that we should wait until we get more confirmation than just second hand info. I would also maybe advise semi-protecting the article in anticipation of vandalism. But I am not sure if preemptive protection violates some sort of policy. --DFRussia (talk) 03:19, 9 August 2010 (UTC)
  • I doubt that this will need protection; even though there's a consensus here not to include the proof yet, that doesn't mean that additions of the proof are made in bad faith. — Gavia immer (talk) 03:56, 9 August 2010 (UTC)
  • Whilst it's definitely premature to claim that Deolalikar's paper proves P!=NP, one possible reason for mentioning the paper would be to show that we (the Wikipedia community) are aware of it. There has been at least one (reverted) edit to add it. There was some discussion of the paper in an IRC channel I inhabit and someone else expressed surprise that it wasn't mentioned in Wikipedia. I was considering adding a reference myself but thought I'd check the history and here first - other editors mightn't. --PeterJeremy (talk) 08:50, 9 August 2010 (UTC)

    I concur; some remark along the lines of "paper exists, is being debated" would seem warranted. After all, it is the most serious contender at the moment. Dysmorodrepanis (talk) 10:44, 9 August 2010 (UTC)

• If anyone cares, there is some discussion of this paper at http://rjlipton.wordpress.com which is a CS theory blog. I don't think it's strictly necessary to wait for a reviewed publication before mentioning it in wikipedia, but yes, it's still way too early right now. If there is a significant amount of informal review by respectable theorists and they have interesting things to say, I think it will be ok to mention it, just not claim that the result has been confirmed unless there is a real consensus among researchers. That is basically what happened with Perelman's paper. FWIW, there have been plenty of serious attempts on the P/NP question by researchers who knew what they were doing in the past, and all have had flaws, so pure Bayesian inference suggests this one also has flaws. In short, one can hope, but don't get too excited. 75.62.4.94 (talk) 04:31, 9 August 2010 (UTC)

  75.62.4.94 is referring to http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ Further discussion about the context of the distribution is at http://gregbaker.ca/blog/2010/08/07/p-n-np/ Jodi.a.schneider (talk) 10:06, 9 August 2010 (UTC)

• I think it would be reasonable to say "A purported proof that P does not equal NP (reference http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf ) is being reviewed by researchers ("A serious proof that claims to have resolved the P=NP question." reference http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ ) for correctness. -- Or something like that. Jodi.a.schneider (talk) 10:14, 9 August 2010 (UTC)
• People have created the article Vinay Deolalikar. It's hard to stop people from mentioning this potential result. /129.142.71.166 (talk) 10:39, 9 August 2010 (UTC)
• How about a whole section on "Notable attempts at proof?" I really think the article needs to mention this, if only to highlight that this is not a complete proof as dcoetzee points out. Infojunkie23 (talk) 10:45, 9 August 2010 (UTC)

Feel free to add such a section. dcoetzee was referring, I think, to a published paper (Deolalikar, Vinay; Hamkins, Joel David; Welch, Ralph (October 2005). "P ≠ NP ∩ co-NP for Infinite Time Turing Machines". Journal of Logic and Computation (Oxford University Press) 15 (5): 577-592. doi:10.1093/logcom/exi022. ISSN 0955-792X. Retrieved August 9, 2010. ), rather than the manuscript currently circulating. Jodi.a.schneider (talk) 10:58, 9 August 2010 (UTC)

Here's a link that might be useful for that: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm --Waldir ^talk 13:00, 9 August 2010 (UTC)

That link is already in the article. Deolalikar's result about infinite time Turing machines (pdf) is interesting but has not much to do with the version of the problem that anyone cares about.

• I very strongly disagree with the fact that there is no mention of this claimed proof in this article. It would only have to be a few sentences that mention that Vinay Deolalikar has claimed to have proven this result and (regularly updated) information on the status of the peer review. Not only is Deolalikar a respected researcher who has proven original results in complexity theory before, but several other leading researchers have described the proof as 'a serious attempt'. Specifically, I think that based on the reception that this news has already received within the computer science community, and the obvious interest in this question on the wikipedia page (including lots of people adding this information and getting reverted) this article needs to at least mention this claimed proof as a current event. Rfrohardt (talk) 13:55, 9 August 2010 (UTC)
  • I'd just like to point out that Vinay Deolalikar has yet to release a final version of his paper. Also, as a computer scientist myself, I would prefer that the paper is battle hardened over time before appearing in an encyclopedia. fintler (talk) 00:14, 10 August 2010 (UTC)

• There are have been tons of failed solutions in the past; here is a list (also mentioned by Waldir above). The one we're discussing is by someone more knowledgable than most, but it's had hardly any review yet. I'm not holding my breath. This has happened plenty of times before, for all the big important open problems. 75.62.4.94 (talk) 15:19, 9 August 2010 (UTC)
  • Nobody is suggesting you hold your breath waiting for confirmation/rejection. If we wanted to include references to other well-known failed attempts I would be in favor of that, and it might actually be a nice addition to the article specifically because it has happened many times, and also because there are several interesting results on how hard it is to resolve P=NP. Obviously saying anything other than "this purported proof is out there and serious people are taking it seriously" would be premature, but considering the buzz this has generated already, I think this is worth addressing in the context of a being a current event/development. I count 9 people trying to add it and getting reverted, and I don't think this is 'vandalism' but people just thinking it is worth adding and not looking at the history or talk page first. Rfrohardt (talk) 15:46, 9 August 2010 (UTC)
    • Wikipedia is not slashdot, and I'm unimpressed by the "buzz" you mention (a slashdot post full of ignorant comments, and posts from more serious blogs (Lipton, Aaronson) where the response is much more skeptical). I expect this proof to be withdrawn or refuted within one week. If that hasn't happened by then I'd be ok with adding a mention. Kempe's failed proof of the 4-color theorem was published in a journal and believed for many years, so asking for this thing to last a week on the internets doesn't seem to be excessive. 75.62.4.94 (talk) 16:13, 9 August 2010 (UTC)
      • FWIW, the one member of our department who took the trouble to look at the paper more closely than just skimming through the abstract (though he did not actually read it) concluded that it is almost certainly bogus. The impression he got from the paper is that there are plenty of definitions, fancy colour pictures, and long-winded prose, but actual mathematical content seems nowhere to be found. One would expect a fair share of calculations and formulas to start showing up at some point (especially since he is relying on very quantitative results like some of Achlioptas' stuff on k-SAT threshold, and combining these with structural results in descriptive complexity), but they are conspicuously missing in the paper. I'm thus deeply skeptical.—Emil J. 16:30, 9 August 2010 (UTC)
  • I think that you make good points and that my excitement as a theoretical computer science student has biased me, nonetheless, I think that claims like "One would expect a fair share of calculations and formulas ... but they are conspicuously missing in the paper" and "I expect this proof to be withdrawn or refuted within one week" are as premature as excitement over the result. I especially don't buy the Bayesian inference argument to doubt this proof. Waiting longer to mention the result on Wikipedia is reasonable, but I don't think that the standard for inclusion needs to be 'conclusively confirmed by experts' but rather 1) significant coverage in the mainstream media and/or 2) consensus among experts that the proof seems reasonably likely to be correct. 138.15.100.103 (talk) 18:04, 9 August 2010 (UTC)
    • I haven't asked for conclusive confirmation by experts, but the current situation is that AFAIK, not a single expert has said even informally that they think the proof looks right. 75.62.4.94 (talk) 20:08, 9 August 2010 (UTC)
• For what it's worth, if we're going to include notable proofs we should probably include the proofs of P=NP by Ted Swart in terms of linear programming in 1986/1987, which were notable enough for them to formally refuted in a general setting by Mihalis Yannakakis. It's the first one mentioned at [6]. Swart's original proof contained a very subtle flaw (see [7]), and I certainly wouldn't rule out that such a subtle flaw exists in this proof as well, although I don't have a sufficient background in statistics to evaluate it myself without a lot of work. Dcoetzee 02:04, 10 August 2010 (UTC)
• If I claim to have proven the conjecture, would you be in favor of including me in the article? Additionally, I am not claiming the author is a crackpot, but may I remind everyone that going public before the results have been peer-reviewed is the first and best indicator of crackpot research. X —Preceding unsigned comment added by 131.130.16.86 (talk) 15:44, 10 August 2010 (UTC)
  • He did not “go public before the results have been peer-reviewed”. He emailed his proof to other mathematicians asking for comments, and one of them leaked it to someone who put it on their blog. It wouldn't have taken you more than a few minutes to learn this (e.g. by reading the entire discussion here), if you'd bothered. DES (talk) 18:51, 12 August 2010 (UTC)
• I am torn here. Certainly, there is no rush to "cover" this: after all, Wikipedia is an encyclopaedia, not a news site. On the other hand, the claim has been taken seriously enough so that a link to an expert evaluation (as opposed to a "post full of ignorant comments") can be provided. The best source, at the moment, seems to be the polymath wiki Deolalikar's P!=NP paper, which aims to centralize the discussion and links to other resources. I think that it's well worth adding it to the references or external links. As a positive side effect, that would relieve the pressure to update the article before things clear up. Arcfrk (talk) 16:30, 10 August 2010 (UTC)
• Not being a mathematician or a computer scientist myself, I am curious why all those in the field are always so quick to label someone with a possible proof a "crank" or "crackpot". Is it so improbable to think that at some point in history a proof will come into existence? —Preceding unsigned comment added by Xcelerate (talk • contribs) 20:34, 10 August 2010 (UTC)
  • Short answer is yes, it's improbable. Even in the cases where the proof was correct the person behind wasn't exactly normal, like Wiles with his insane obsession and secrecy, or like Perelman who posted the proof somewhere on arXiv and didn't care for a whole three years (!!!) and then rejected the 1mil prize (!!!). Except for this, 95% of the papers claiming to have such proofs are written by clear crackpots (RH suffers the most from it). Another 4.9% suffer from a small oversight which almost always destroys the proof. Only 0.1% of these "groundbreaking" papers are correct (they still have errors, but they're minor). Besides, 40 years is not so much for a such hard problem in a such new field. This paper however, has a lot of potential even if the proof itself is bogus, because it does present a few interesting ideas. Max (talk) —Preceding undated comment added 21:18, 10 August 2010 (UTC).

Potential solution: break

• Not mentioning the proof by a single word in the article is just downright stupid. The mention does not have to credit or discredit the proof. There are a bunch of wrong proofs given for a number of problems over time and they have mention about the most famous attempts in their articles. As the normal visitor amounts to this article has become eightfold lately the public clearly is interested in this article exactly because of the circulating proposed proof and thus a good mention of the still very speculative nature of the proof should be incldued http://stats.grok.se/en/201007/P_versus_NP_problem . Gillis (talk) 14:25, 11 August 2010 (UTC)

  I tend to agree. This attempt has certainly received significant coverage in multiple reliable sources and hence is notable. That is the necessary requirement for inclusion. I have tentatively added a section on notable attempts to the article. — Martin (MSGJ · talk) 17:02, 11 August 2010 (UTC)

  Wikipedia is not a newspaper. I fail to see the incentive to put the mention of the manuscript here until the dust settles. Once peer reviews will come in a clear picture will form, and this manuscript will find its way here if it's justified. You can rest assured about that. IIRC Perelman's proof was on arXiv for three years and no one cared one bit (except for the people involved), what's the rush now? Max (talk) —Preceding undated comment added 19:17, 11 August 2010 (UTC).

  Because regardless of whether or not the proof is successful, the attempt is undeniably notable and thus qualifies for inclusion. No, we are not a newspaper but we are not a conventional encyclopedia either and we can be up-to-date. Our readers expect an up-to-date encyclopedia article and I suggest that this attempt should form part of that. — Martin (MSGJ · talk) 08:15, 12 August 2010 (UTC)

  I agree that the manuscript has gained much public attention, furthermore, I think that this manuscript will have an actual impact on the field even if it's fatally flawed. However, why not open an article on Wikipedia which will list all important manuscripts regarding P=?NP ? Deolalikar's manuscript can be included there, along with other important papers, like Yanakakis's paper and Swart's papers. As the matter stands, whether the paper is correct is still in the speculation phase, while Wikipedia should strive to publish only well known facts or widely accepted views on a scientific article. Max (talk) 13:50, 12 August 2010 (UTC)

  Yes, and I would encourage you to add other notable papers to P versus NP problem#Notable attempts at proof (I think a separate article would only be appropriate if that section got too long). We are only publishing well known and verifiable facts, i.e. that this attempt has been made and its correctness is yet to be verified. Just because not everything is known about a topic is not a reason to exclude what is known. — Martin (MSGJ · talk) 14:08, 12 August 2010 (UTC)

What?

Um, what is this? Articles usually start off with "The P versus NP Problem is..." followed by a description that it not too technical for the average reader... Sephiroth storm (talk) 00:38, 10 August 2010 (UTC)

Good point, the intro really does need work. I rewrote the first sentence but will have to do some other things soon. 75.62.4.94 (talk) 01:01, 10 August 2010 (UTC)

I added a less formal definition of P and NP closer to the lead. Unfortunately, this means that we return to defining the same terms three times in the same article, in increasing detail, but at least it should be possible to skim the lead section for a basic understanding now. — Gavia immer (talk) 01:51, 10 August 2010 (UTC)

Some more tightening is possible but in any case it's more readable now than it was before. The whole article could actually use cleanup and polishing. It's quite an important article but currently a bit haphazard. 75.62.4.94 (talk) 06:57, 10 August 2010 (UTC)

I've rewritten the intro, putting more emphasis on the real world impact of this unresolved question, so that it's importance is easier to grasp by people who neither know maths, nor care about maths. IMO, this article should be able the 'problem', its implications, and ongoing progress on the solution, and leave the difficult 'explain the maths' to be covered in more detail in the articles about complexity theory. John Vandenberg ^(chat) 05:05, 13 August 2010 (UTC)

Please improve the layman section

Why is the following problem not a member of P? Find the Man in the Yellow Hat: Curious George likes to lie. He will say someone is not the man in the yellow hat when he is, but he won't say he is the man in the yellow hat if he isn't. The first time you ask George he has a 100% chance of admitting it is the man in the Yellow Hat if it is. Each time after his odds of getting him to admit it, drops by 50%. BTW. I think I understand why it is not part of P, but it is not clear from the layman section. 24.36.199.169 (talk) 13:38, 11 August 2010 (UTC)

Mentioning decision problems in the lead

I just undid an edit by 91.193.157.170, which (effectively) changed all mentions of "decision problems" to just "problems", "certificates" with "solutions", etc. — a more informal statement of the question. I believe stating it precisely is important to avoid confusing readers, but if someone thinks that just talking of "problems" is simpler and "good enough", feel free to re-do. Shreevatsa (talk) 03:12, 13 August 2010 (UTC)

It is a matter of decision problems, and not general function problems, and we ought to state that plainly, so I think your revert was correct. Moreover, we do mention the function problem version at the end of the lead. Of course, in either case it's the underlying algorithms that get the attention, and not the particular form of the result. We ought to feel free to handwave the decision step anywhere that it doesn't add to the explanation, but we shouldn't simply ignore it. — Gavia immer (talk) 03:51, 13 August 2010 (UTC)

I agree with your revert, and would prefer 'decision problem' to be visible in the intro without being hidden under 'problem with a yes-or-no answer' as I attempted in my revision (which you reverted) John Vandenberg ^(chat) 05:21, 13 August 2010 (UTC)

Oh sorry, I didn't notice I was reverting your edit. But looking it at now I think you should discuss your edit separately; e-commerce and cryptography don't generally rely on the hardness of NP-complete problems but that of problems like factoring and discrete log which are believed not to be NP-complete. Shreevatsa (talk) 05:51, 13 August 2010 (UTC)

No worries; I was nearly going to put it here on the talk for discussion anyway.

wrt to PKC, arn't these cryptographic algorithms still in NP (ignoring which subclass they reside in)? i.e. the verification algorithms need to be feasible in order to be usable for PKC in the real world. We list PKC in the section P versus NP problem#Consequences of proof, and factoring in NP (complexity)#Examples. John Vandenberg ^(chat) 10:16, 13 August 2010 (UTC)

The normal use of cryptographic algorithms is in P. Cryptanalysis (attempts to break the cipher and get the key or plain text by an unauthorized person) is intended to be difficult, and is in NP. But for practical crypto-systems, cryptanalysis is not known to be NP-complete at this time.

However, the danger to cryptography of finding that P=NP is far overshadowed by the immense benefits that would be enjoyed by other computational applications. JRSpriggs (talk) 11:55, 13 August 2010 (UTC)

The edit had nothing to do with "decision problems" vs "problems", etc.

The introduction currently refers to problems *with a yes/no answer*. However, it does not become clear why only this kind of problems is relevant. In fact, if you can easily check the answer of a yes/no problem, then you can easily compute it - just check the 'yes' answer, then the 'no' answer.

When I originally fixed this, I included a reference to the Clay Mathematics Institute page on the problem, which supports my version of the introduction, but which nobody seems to have bothered to check. See here: http://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof for a reason why that institute's definition of the problem can be trusted.

Since the article in its current state does not make sense (possibly unless one is familiar with some very specific and counter-intuitive terminology, in which case one wouldn't need this article), I am redoing the edit. Before undoing it again, please give a valid and logical reason why my argument is wrong. 91.193.157.170

And indeed you have. It's a good idea to discuss first before re-doing a change (the bold-revert-discuss cycle), as not doing so can lead to edit wars. Anyway, to (re-)start the discussion: you are right that it's not the answers ("Yes" or "No") that can be easily checked, but certificates, which are "proofs" for the yes case. It is part of the definition of P and NP that they only refer to problems "with a yes/no answer" (but as the paragraph you removed says, FP v/s FNP is equivalent to P vs NP). I'll leave it for others to discuss, but hopefully the end result will be something that clear to all. Shreevatsa (talk) 22:15, 13 August 2010 (UTC)

"It's a good idea..." - I completely agree with you on this. In this specific case I breached the rules because everybody seemed to have misunderstood the point of the edit.

I also agree with your other points. However, the article in its previous state was confusing for people lacking your mathematical background, as I believe I showed in the 2nd previous post. Please note that due to the recent attempt at a solution, this problem has become popular, and we cannot expect everybody who searches for it to know as much as you.

I promise not to edit this page any more, my intentions were far from starting an edit war. 91.193.157.170

Proof of a computation versus proof of computability

At the end of section P versus NP problem#Polynomial-time algorithms, it says "However, this is only guaranteed to work if there is a provable polynomial time algorithm for SUBSET-SUM; one might imagine an algorithm which works but cannot be proved to work.". Assuming subset sum is in P, it is possible that there might not be a proof (in ZFC, say) of that fact. However, for any specific computation in polynomial time that finds a subset (which adds to zero) of a specific set, there will be a proof of that fact and that proof can be done in polynomial time. It is this latter proof which is at issue here. JRSpriggs (talk) 19:32, 13 August 2010 (UTC)

Yeah, that's why I had removed it. The section could be written more clearly, but the algorithm would be polynomial-time as long as P=NP is true as a fact, whether we can prove it or not. Shreevatsa (talk) 22:22, 13 August 2010 (UTC)

Actually, the whole part (starting at "Perhaps") is confusingly written. It just says, in convoluted terms, that P is closed under complement. (Thus if P=NP, then P=NP=coNP=NP∪coNP=NP∩coNP, so SUBSET-SUM can be decided in polynomial time.) And this is just stated, not (effectively) explained. How about trimming it? Shreevatsa (talk) 00:47, 14 August 2010 (UTC)

Yes, I looked at it again and realized that it is (in part) claiming that if the answer is "no" and P=NP, then one can prove that the answer is "no" in polynomial time. That may not be possible because there is no polynomial which is an upper bound for all polynomials, so I deleted the second algorithm. JRSpriggs (talk) 02:00, 14 August 2010 (UTC)

No, the claim is correct. As I said, if P=NP, SUBSET-SUM is also in co-NP, so a proof that there is no subset adding up to 0 exists and can be found in polynomial time. The algorithm actually works (there is a polynomial bound on a proof of either Yes or No), but the explanation was unclear. Shreevatsa (talk) 02:11, 14 August 2010 (UTC)

Sorry. JRSpriggs (talk) 16:32, 14 August 2010 (UTC)

This is wrong. Of course, for any input S of a polynomial-time algorithm there is a polynomial-time constructible proof that the algorithm gives such-and-such output on S. However, there is no way to conclude from this that we have a polynomial-size proof that S is not in SUBSET-SUM, unless we can prove that the algorithm is correct.—Emil J. 12:53, 16 August 2010 (UTC)

That is, you are right that the needed assumption is slightly weaker than having a provably correct P-algorithm for an NP-complete problem: your argument works assuming that (1) there exists a coNP-algorithm which provably solves an NP-complete problem (which implies that both positive and negative instances of SUBSET-SUM will have poly-size proofs) and (2) P = NP (which implies that these proofs can be find in polynomial time). However, I don't see this to make much of a difference, and in any case you still need to assume the provability of something.—Emil J. 13:54, 16 August 2010 (UTC)

No, you don't need. Suppose P=NP. Then because P is closed under complement, coNP=NP=P as well. So (because SUBSET-SUM is in P), you have a polynomial-time algorithm (say $p_{1}(n)$ steps for input of length n) accepting SUBSET-SUM, and (because (SUBSET-SUM)^∁ is in NP) you have a polynomial-time algorithm (say $p_{2}(n)$ steps) accepting SUBSET-SUM^∁. Just run these two in parallel, and you have a polynomial-time algorithm (in $2\max(p_{1}(n),p_{2}(n))$ steps) deciding SUBSET-SUM. (You don't have to actually run the two in parallel because the algorithm is the same, but whatever.) Nowhere do you need to assume the provability of something. (Of course, to prove an actual bound on the running time of the algorithm, you need an actual bound on the running time of SUBSET-SUM -- but you don't need any provability to say that "If P=NP, this algorithm is polynomial-time as well".) Shreevatsa (talk) 17:12, 16 August 2010 (UTC)

Sigh. Recall that we are discussing this algorithm:

FOR N = 1...infinity
FOR P = 1...N
Run program number P for N steps with input S
IF the program outputs a complete math proof
AND each step of the proof is legal
AND the conclusion is that S does (or does not) have a subset summing to 0
THEN
OUTPUT "yes" (or "no") and HALT

It obviously solves SUBSET-SUM, and you claim that assuming just P = NP, this algorithm runs in polynomial time. In order for this to be the case, you have to establish (among others) that for any input S ∉ SUBSET-SUM, there exists a "complete math proof" (let's make this precise by asking for a proof in ZFC) of the statement

(*) no subset of S sums to 0

of size polynomial in the length of S. Where did you show that? I see a lot of talk about algorithms in your post, but you did not show the existence of any proofs.

Now, here is where I suspect your confusion is. If P = NP, then there is an algorithm, lets call it A, which solves SUBSET-SUM in polynomial time. Then, given S as above, we can find in polynomial time a polynomial-size ZFC proof of the statement

(**) algorithm A rejects input S.

That's all very nice, but (**) is not (*). The only way I can see to construct a ZFC proof of (*) from a proof of (**) is to use a ZFC proof of the statement

(***) A does not reject any positive instances of SUBSET-SUM,

i.e., (half of) the statement of correctness of A. If there is another way, show it.—Emil J. 17:57, 16 August 2010 (UTC)

(edit conflict) Oh, that algorithm is pretty poorly written, and it's not worth discussing it in too much detail. As I've been saying, the conclusions were correct, but the section was unclearly written. So let's rewrite it properly, without talking of "complete math proofs" unless necessary, since they can lead to confusion like the questions you raise. (In fact, the algorithm is actually correct: in either case there is a certificate of polynomial length, which can be verified in polynomial time, so there is always a polynomial-length "proof", which can be quite easily converted to a formal proof in ZFC. For instance, for the case of YES instances, the proof would involve what the earlier algorithm says: "the program outputs a list of distinct integers AND the integers are all in S AND the integers sum to 0", then you can mechanically convert that into a proof. For the case of NO instances, it's not immediately obvious what such a proof would look like, since we don't know or believe SUBSET-SUM is in coNP, but if P=NP, then there is always such a proof. But it's better to avoid mention of proofs and ZFC altogether if possible, because that sort of detail is not germane to the point here.) Shreevatsa (talk) 18:31, 16 August 2010 (UTC)

You keep asserting the existence of proofs without justification, and as far as I can see, you are wrong in both places where you do so. You need to prove in ZFC the correctness of the algorithm in order to convert a certificate for the NO instances into a ZFC-proof. You don't need it for the YES instances because summing to 0 is ZFC-provably polynomial-time decidable. The algorithm is correct, but not necessarily polynomial-time.

Because SUBSET-SUM is in NP, there is a polynomial-time certificate for the YES instances — which, along with its verification, is a proof. If SUBSET-SUM is in coNP (which we assume when we assume P=NP), there is a polynomial-time certificate for the NO instances — which, along with its verification, is a proof. Shreevatsa (talk) 19:04, 16 August 2010 (UTC)

It is a proof of "this-and-this algorithm accepts S". It is not a proof of "S is not in SUBSET-SUM".—Emil J. 10:40, 17 August 2010 (UTC)

PS, after seeing your second edit. No, we don't currently know a way of giving a proof of (*) — obviously, since we don't believe that that SUBSET-SUM is in co-NP. But if P=NP, then if we can "accept" SUBSET-SUM we can "decide" SUBSET-SUM as well, because P=coP. That's all I've been saying! (But let me ask: why do you say (**) is not (*)? If A is correct—and it is, because we already have proved that A is correct if P=NP—then (*) is equivalent to (**).) Shreevatsa (talk) 18:31, 16 August 2010 (UTC)

Huh? (**) is a different string of symbols than (*). The algorithm above cannot check whether something is equivalent in the real world, it can only check that the proof is formally correct as written. By your argument every true statement would be trivially provable, on account of being equivalent to 0 = 0. We didn't prove anything about A, we assumed that it solves SUBSET-SUM.

We are discussing the running time of the algorithm above, because that's what was incorrectly stated in the article. We are not discussing that P = NP implies P = coNP, which you keep bringing up for reasons which escape me. But regarding the sentence you wrote above: if P = NP, then we can decide SUBSET-SUM, period, we don't need to further "assume" that we can accept SUBSET-SUM.—Emil J. 18:50, 16 August 2010 (UTC)

If you prove A is correct, and you prove A rejects an instance, doesn't it prove (*) for that instance? (1) We have (or rather Levin has) already proved that A is correct if P=NP. (A being the algorithm currently mentioned in the article.) (2) You accept that we can prove that A rejects an instance. So from (1) and (2), isn't this a proof of (*)? Anyway, you agree that "if P = NP, then we can decide SUBSET-SUM, period". Which was the point of this whole discussion. So let's keep it in the article (which I see was done a few hours ago). So all is good. Shreevatsa (talk) 19:04, 16 August 2010 (UTC)

What you say here does not make any sense to me. Recall that A was a hypothetical algorithm which solves SUBSET-SUM in polynomial-time, which exists by definition assuming P = NP. Nobody proved it correct, it is not even an explicit algorithm. You seem to be talking about something else.—Emil J. 10:40, 17 August 2010 (UTC)

I mentioned that A for the specific (Levin's) explicit proved-correct algorithm, not a hypothetical algorithm. But this doesn't matter now, since I see I made a mistake (below). Shreevatsa (talk) 19:42, 17 August 2010 (UTC)

After some thought, I think I see more clearly where the confusion is (and why the algorithm that was removed is actually correct). Consider the following two algorithms for SUBSET-SUM, which I'll call A1 and A2. A1 is the algorithm in the article, whose idea is attributed to Levin:

   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a list of distinct integers all in S and they sum to 0,
           THEN
               OUTPUT "yes" and HALT

A2 is:

   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a proof that S ∈ SUBSET-SUM,
           THEN
               OUTPUT "yes" and HALT

Now we all agree that if P=NP, then A1 is correct (accepts precisely SUBSET-SUM) and runs in polynomial-time. What about A2?

• 1. If there is a program that in polynomial-time can output a subset, then there is another slightly different program that in polynomial-time can output a proof: just output the subset along with some verification that it all adds up to 0. So A2 is correct (accepts precisely SUBSET-SUM) and runs in polynomial time.

• 2. Nowhere in the definition of A2 did we use any property of SUBSET-SUM other than the fact that it's in NP. It seems that A2 would work if we replaced SUBSET-SUM with any other language L in NP. That is, define an algorithm A3, parametrized by language L, is as follows. A3(L) is:

   FOR N = 1...infinity
       FOR P = 1...N
           Run program number P for N steps with input S
           IF the program outputs a proof that S ∈ L,
           THEN
               OUTPUT "yes" and HALT

A2 is just A3(SUBSET-SUM). I claim that for any language L in NP, A3(L) is an algorithm that accepts precisely L, and runs in polynomial-time if P=NP. Whatever the structure of L is, or the reason why it's in NP, there is some program that will output a proof using a certificate for whatever predicate puts L in NP. (More formally: L, being in NP, is defined by some polynomial-length predicate $\phi$:

$L=\left\{x\mid \exists c{\mbox{ s.t. }}\phi (x,c)\right\}$

and the program would output the certificate c along with a verification that $\phi (x,c)$ holds, which is a proof that $x\in L$.)

• 3. Now, if P=NP, then (because coNP=NP), ${\overline {\mbox{SUBSET-SUM}}}$ is such a language L. So the algorithm $A3({\overline {\mbox{SUBSET-SUM}}})$ is an explicit algorithm that accepts precisely ${\overline {\mbox{SUBSET-SUM}}}$, and runs in polynomial time.

• 4. Let A4 be the following algorithm: run $A3({\mbox{SUBSET-SUM}})$ and $A3({\overline {\mbox{SUBSET-SUM}}})$ in parallel (one step each, say). If the former accepts, OUTPUT "yes" and halt. If the latter accepts, OUTPUT "no" and HALT. I claim that A4 is an explicit algorithm that decides SUBSET-SUM. (Note that we assumed P=NP to prove both correctness and polynomial-time, whereas earlier we were assuming P=NP only to argue polynomial-time. But this doesn't matter.)

• 5. The algorithm that was previously in the article is equivalent to A4.

If I've made a mistake, I'd like to know about it. Else, I feel it was unnecessary to remove the algorithm that was in the article. Thanks, Shreevatsa (talk) 20:16, 16 August 2010 (UTC)

First, wherever you say that A1, A2, etc. run in polynomial time, it actually mean that they accept positive inputs in polynomial time, but runs forever for negative inputs; I assume we agree on this point, but just to make the terminology clear.

Yes, agreed.

The error in your argument is that your A3(L) is not well-defined. You cannot explicitly produce an algorithm like this for a given NP-language L, you can only do it for a given NP-algorithm. Thus your notation $A3({\overline {\mbox{SUBSET-SUM}}})$ is meaningless until you specify an explicit NP-algorithm for ${\overline {\mbox{SUBSET-SUM}}}$. You cannot do that using just P = NP, since that does not give you beforehand an explicit poly-time algorithm for SUBSET-SUM, it only says that an algorithm exists. You can realize your error very easily: just avoid all these abbreviations like An, and try to write down your "explicit algorithm" explicitly.

Ah thanks! Finally, I see my mistake. Thank you very much. Sorry. :-) You are right, A3(L) is not explicit unless we know the predicate for L. That is, even though L is defined as "x such that φ(x,c) is true for some c", and there will exist a program outputting a proof of "there exists c such that φ(x,c) is true" given an x, we would not recognise it as a proof of x being in L. So only something like A3(φ) can be explicit, not A3(L). This is what I somehow missed. The non-explicitness in "IF the program outputs a proof that S ∈ L" is in the "IF"! Even though the program is outputting a proof that would be the same as S∈L if we knew about L, it is not a proof of S ∈ L, and we can't recognise it unless we do know it's equivalent. Oops. This is what you've been saying. Thanks. Shreevatsa (talk) 19:42, 17 August 2010 (UTC)

Great. I'm glad we are finally tuned to the same frequency.—Emil J. 09:53, 18 August 2010 (UTC)

The second error is that the algorithm that was in the article is not equivalent to A4. You still seem to be incapable of understanding that differently formulated statements are different objects even though they have the same extension in the real world. A proof of the statement "S is not in SUBSET-SUM" is something quite different from a proof of "S is accepted by M" where M is an NP-machine which happens to solve ${\overline {\mbox{SUBSET-SUM}}}$. The best you can do is that you can transform one of the proofs into the other if you have a proof that M is correct.—Emil J. 10:04, 17 August 2010 (UTC)

Well, it doesn't matter now, but modulo my earlier mistake, they are the same. A4 has two threads in parallel, one which runs programs waiting for a proof of S ∈ L and one which runs programs waiting for a proof of S ∉ L (which now I realise isn't possible, but that's how I had defined A4), but both of these threads are running the same programs. The algorithm that was in the article just has one thread that runs programs waiting for a proof of either S ∈ L or S ∉ L, so they are equivalent. Anyway, thanks for pointing out the error. Shreevatsa (talk) 19:42, 17 August 2010 (UTC)

Also, let us keep in mind that the correctness of A2, A3(L), etc., assumes the consistency of the formal system whose proofs are referred to in the algorithm (otherwise the algorithm will accept all inputs). This may become a problem if the system is strong enough.—Emil J. 12:45, 17 August 2010 (UTC)

To Shreevatsa: Please provide a proof (not relying on the things in dispute here) or on-line reference for "if P=NP, then coNP=NP". JRSpriggs (talk) 18:55, 17 August 2010 (UTC)

This is trivial: P is closed under complementation (that is, a language is in P iff its set-theoretic complement is) so if P=NP then NP would also be closed under complementation because it would be the same class as P. I'm sure there are references out there somewhere that say this explicitly but it seems to me to be the sort of trivial calculation that doesn't need a reference. —David Eppstein (talk) 19:04, 17 August 2010 (UTC)

To David Eppstein: Forgive the stupid question, but how do you know that P is closed under complementation? JRSpriggs (talk) 19:35, 17 August 2010 (UTC)

Suppose that A is a polynomial-time algorithm for a decision problem in P. Let algorithm A' be the algorithm that runs algorithm A and then returns the Boolean negation of its answer. Then A' is a polynomial-time algorithm for the complementary problem. —David Eppstein (talk) 19:58, 17 August 2010 (UTC)

So are all these complexity classes defined to be subclasses of the class of recursive sets? Or recursively enumerable sets? Or what? JRSpriggs (talk) 23:35, 17 August 2010 (UTC)

They're certainly subclasses of both of those families, whether or not they're explicitly defined that way. Is there a point to these naive questions? —David Eppstein (talk) 00:00, 18 August 2010 (UTC)

Well, I had thought I knew what these classes were. But after trying to read the argument above, I realized that I am confused. So I am trying to attain clarity.

In particular, what would it mean for subset-sum to be in P? Suppose there is an hypothetical (1st) algorithm that solves subset-sum in polynomial time and always returns either "yes" or "no" when it halts. If it can be proved to have that property, then certainly the (2nd) algorithm using proofs should do the same thing. Right?

Right. The problem was whether the assumption that "it can be proved to have that property" is actually needed.—Emil J. 09:53, 18 August 2010 (UTC)

However, I am wondering why the (3rd) algorithm which is currently in the section and searches through sub-calculations including sub-calculations of the (1st) algorithm is allowed to loop forever when the answer is "no". That seems contrary to your definition of P which requires that it always halt with either "yes" or "no". JRSpriggs (talk) 00:32, 18 August 2010 (UTC)

There is no difference in algorithmic power between, on the one hand, deterministic polynomial time algorithms that always halt with a yes or no answer and, on the other hand, deterministic algorithms that halt in polynomial time with a yes answer and go into an infinite loop on a no answer. The reason for this equivalence is that an algorithm of the first type can be transformed into an algorithm of the second type trivially (by checking whether the answer is no and if so going into an infinite loop) and that an algorithm of the second type can be transformed into an algorithm of the first type less trivially (by counting how many steps it performs, as it performs them, and aborting the computation and returning no whenever the count exceeds the polynomial bound on the number of steps it should take to return a yes answer). This is all very standard. —David Eppstein (talk) 00:46, 18 August 2010 (UTC)

To clarify a potential misunderstanding: in order to perform the latter transformation, we need to know the bound on the running time of the algorithm of the second type (on yes instances). Thus an explicit algorithm of the second type does not necessarily give us an explicit algorithm of the first type, which is what made possible all this discussion.—Emil J. 09:53, 18 August 2010 (UTC)

Notable proof attempts

The "Notable proof attempts" section needs expansion. Can anyone add some based, perhaps, on http://www.win.tue.nl/~gwoegi/P-versus-NP.htm ? Based on comments in earlier threads it could include:

• Ted Swart (see also http://mat.tepper.cmu.edu/blog/?p=767 )
• Edward Nelson (see also http://rjlipton.wordpress.com/2009/08/20/what-will-happen-when-pnp-is-proved/ )

Jodi.a.schneider (talk) 19:41, 15 August 2010 (UTC)

I'm not convinced these really are notable. I can't find anything about them in Google news, for instance. This whole section appears to me to be nothing more than a post facto rationalization for ignoring WP:NOTNEWS. —David Eppstein (talk) 23:16, 16 August 2010 (UTC)

Maybe a separate section is not the answer then, but the article needs to cover milestones in the history of the problem somewhere. See second para of Fermat's Last Theorem for an example.Infojunkie23 (talk) 07:47, 17 August 2010 (UTC)

Slightly tangential comment: We need to be careful not to insert the WP sense of the word notable into article space. Whether the attempts are notable in the sense of the WP term of art is quite a different question from whether notable is the best word to describe them in an encyclopedia. I'm not necessarily saying it isn't the right word. Just that we all need to be on our guard not to be influenced by the WP usage when choosing words for article space. --Trovatore (talk) 10:26, 17 August 2010 (UTC)

Agreed. Actually I'm sufficiently concerned about that point that I think the word should be avoided, ceteris paribus. CRGreathouse (t | c) 14:35, 17 August 2010 (UTC)

I also agree none of these attempts seem notable, and the section should be removed. (though it's probably easier to remove it eventually, when all this settles down.) Fermat's Last Theorem is different because it has already been proved, so mathematicians can with hindsight decide what the milestones were and what were the dead ends. :-) Shreevatsa (talk) 19:45, 17 August 2010 (UTC)

• I'd like to get rid of this section. I think it is either misconceived or in poor taste. We should retain a mention of the Deolalikar incident because it's still of some current interest and the Deolalikar biography AfD closed to merge the content here, but should retitle the section and not add other such stuff without good reason.

  The actual situation is that P vs NP, like FLT and other famous math problems, has generated a huge amount of research attempting to solve it but ending up proving lesser results (or in some cases creating research directions more important than the original problem). Researchers working on P vs NP are constantly publishing papers on whatever progress they make without claiming they actually solved P vs NP. Those are proof attempts that actually accomplish something, they're just not written up as "proof attempts". The proof attempts section currently in the article (and with its suggested expansion) is really a "list of confused researchers who incorrectly thought they had proved P!=NP" and as such it's a bit tacky. We have a list of published false theorems but that's limited to theorems that actually made it into edited journals. I don't think we need to worry about mistaken proofs that were rejected or withdrawn before publication.

  I'd also point out that while Swart, Nelson, and Deolalikar are all professional mathematicians, none of them are complexity theorists, and as such may have made mistaken claims based partly on not understanding (the way specialists do) how hard the P vs NP problem really is. In sports terms, solving P vs NP is like accomplishing a ten-foot high jump. These "attempts" are not like 8 or 9 foot jumps that didn't reach 10 feet, since when someone jumps 8 feet (which is still remarkable) they normally announce it as an 8 foot jump. Papers like Deolalikar's are more like when a professional soccer player does a 120 cm (about 4 foot) jump, thinks "ok, I guess low-profile track and field events like the high jump doesn't attract as good athletes as major sports like soccer", and announces they did a 10 foot jump, when they really had just gotten confused and thought 1 foot was 10 centimeters instead of 12 inches. Someone who can actually jump 7 feet has had a lot of high-jump practice and coaching, and as such, has a better understanding of the difficulty of reaching 10 feet and knows to check any claim very carefully. It's the same way with complexity theorists and P vs NP. 67.122.209.167 (talk) 22:40, 17 August 2010 (UTC)

• I see the section has been renamed "attempts at proof". That is still misleading since the section is really about "erroneous claims of proof". There are many "attempts at proof" by researchers who don't make such errors, they just say (at most) "I tried such-and-such approach and it didn't work". The erroneous claims are not of much intrinsic interest and this most recent one only got a lot of attention because of some errors of judgement of certain bloggers when it first started circulating. 67.122.209.167 (talk) 04:00, 18 August 2010 (UTC)

• I have rewritten the section and changed its title to "proof announcements". I think the text could use improvement but that it's an ok start, and I like the new approach and title better. If you change the title again, please make sure to also fix the anchor in the redirect now at Vinay Deolalikar. 67.122.209.167 (talk) 05:41, 18 August 2010 (UTC)

I have undone some of your changes, since they are mildly POV and contain a bias against such proof attempts. It's not fair to say that consensus has emerged that the proof is incorrect meaning it can't resolve the concerns or is completely useless. The proof has not been peer reviewed yet. http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/ says "Yogi Berra said, “It ain’t over til it’s over.” To judge from the discussions reported above, it ain’t over. This is so even with the passing of some days since the community has determined that the answers to the first two of Tao’s three questions which we headlined on Wednesday is “No”, and most probably likewise the third." So please don't declare final judgement prematurely. It's unfair either to say that these are not real attempts but merely "announcements". --rtc (talk) 09:34, 18 August 2010 (UTC)

Note that anchors and section names are independent. I have put there an explicit anchor so that we do not have to worry about breaking the link should the section named change. There is in fact no reason to keep a separate section just because of the redirect, the anchor can be put anywhere in the text if we choose to get rid of the section and only mention Deolalikar in passing.—Emil J. 10:05, 18 August 2010 (UTC)

Oh, nice. Thanks. 67.122.209.167 (talk) 16:46, 18 August 2010 (UTC)

I don't think Rtc's partial reversion is appropriate. First of all the section title "notable proof attempts" is really wrong, for reasons stated earlier, and even more so with the current text (even after rtc's edit) since most of the announcements on Woeginger's page are not notable. I don't understand what Rtc means by "merely announcements". If someone says "I have solved P vs NP", that is an announcement (maybe not a correct one), and that is what the section documents. And it's not "mere": "announcement" is a perfectly neutral description. If someone works on the P vs NP problem and ends up (say) inventing descriptive complexity, that is an attempt, which is not what the section is about. Second, Deolalikar's proof is really all but dead as a proof, though there's some chance of a useful idea or two emerging from it. My old wording wasn't the greatest and adding a little more nuance to it would have been fine, but I think Rtc (and to some extent Lipton) are overstating the current status of D's proof. It will only really be "over" if D. himself withdraws it, which he might never do. As Lance Fortnow explains,[8] "Deolalikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects." Now what? 67.122.209.167 (talk) 16:35, 18 August 2010 (UTC)

"If someone says "I have solved P vs NP", that is an announcement (maybe not a correct one), and that is what the section documents. I don't see what's "mere" about it--"announcement" is a perfectly neutral description." Not at all neutral. It's a description that focuses on the act of announcing "I have solved P vs NP", neglecting that there is a proof taking up quite some space compared to this mere announcement. "Second, Deolalikar's proof is really all but dead as a proof, though there's some chance of a useful idea or two emerging from it." That's your view. Fact is Deolalikar claims to have a proof and fact is there are some (notable researchers) claiming to have found invalid reasoning in this proof that is impossible to fix. But neither has Deolalikar himself acknowledged that there is a fundamental problem nor has any peer review been done to reject this proof. So we should report both views and not claim one of them to be correct. "but I think Rtc is overstating the current status of D's proof." Even if that should be true, it doesn't justify to fix this problem with nebulous statements like "consensus emerged that the proof was incorrect". Most people are probably open on that question and are ready to give Deolalikar some more time to cope with the counter-arguments before final judgement is made. "It will only really be "over" if D. himself withdraws it, which he might never do." We do not need to speculate about that. If people start writing in their blogs "Deolalikar is irrationally ignoring major lines of criticism" instead of "It ain’t over til it’s over" we can discuss that again. "Now what?" Let's stick to the facts and not declare final judgement has been made or can be foreseen. --rtc (talk) 18:19, 18 August 2010 (UTC)

1. Yes, "announcement" focuses on the act of announcing. It is a neutral term for describing that act. The section is about announcements, precisely that. Not about proofs or attempts at proofs. It's not about (correct) proofs since no proof has been found. It's not about attempts at proofs since most of those (including very substantial ones, like Sipser's multi-year investigation of circuit lower bounds) aren't described that way in the resulting publications; as such, the whole concept of "attempts at proof" as an encyclopedic topic is misconceived. The section is about papers whose authors have purported are proofs but that haven't been accepted as such. If you've got a different word than "announcement" for that, then ok, but "attempted proofs" is really not appropriate.
2. "Consensus emerged" is from the cited NYT article. A bit of expansion (including quoting Lipton) would be fine, and we should mention that D. has not withdrawn the claim, but frankly I think you're being a bit tendentious in saying D's proof has not been peer reviewed, given the amount of examination that's taken place and found apparently-unfixable holes. You may also be misinterpreting Lipton, whose reading of the mathematical situation is (as far as I can tell) about the same as everyone else's, but who has adopted a deferential writing style that (sort of like the Wikipedia arbitration committee's ;-)) makes it a bit too easy to confuse purely formal possibilities with plausible real-life events. FWIW, Bill Gasarch ([9] #7) has rather forcefully called for withdrawal by August 26 and says "[t]he only real news I can see happening at this point is a retraction". Gasarch's summary of the situation is pretty accurate in my opinion.

Can I ask what it will take to get you to say "it's over", if a) D. doesn't withdraw the proof (e.g. he keeps writing revised versions of the paper, like Swart did); b) nobody actually comes out in public and writes "D. is irrationally ignoring major lines of criticism" (they just stop posting about him instead); and c) the paper is not formally refereed by a journal (editors have the discretion to reject unpromising papers without bothering referees with them) so by your apparent standards it won't have been peer reviewed? I think the main TCS bloggers who have written about this affair are Aaronson, Fortnow, Gasarch, and Lipton (am I missing anyone? We could add Gowers, though great as he is, I don't think of him as a TCS guy) and I just don't see a whole lot of difference between them about the proof's mathematical prospects. 67.122.209.167 (talk) 20:22, 18 August 2010 (UTC)

1. "It's not about attempts at proofs since most of those (including very substantial ones, like Sipser's multi-year investigation of circuit lower bounds) aren't described that way in the resulting publications" That doesn't hinder us to say that they actually are attempts or have developed out of attempts. They are not mere "announcements", they are attempts to prove the thing, perhaps accompanied with such announcements, though not always. 2. "but frankly I think you're being a bit tendentious in saying D's proof has not been peer reviewed, given the amount of examination that's taken place and found apparently-unfixable holes." There's no question about that, it simply has not been peer reviewed. It has been looked at, quite carefully, by quite competent researchers, and serious problems seem to have been found. But the proof has not yet been sent to a journal and has not been formally peer reviewed in this sense. Don't be unjust. One doesn't accept affirmative arguments if outside of formal journal refereeing as peer review, so one shouldn't accept negative argumments made in such a way as peer review. "makes it a bit too easy to confuse purely formal possibilities with plausible real-life events" Besides that I do not think that a possibility can be "purely formal", you seem to have the same misunderstanding with respect to what I write. Let's make this clear: I think that the points made have very serious implications for the proof and that it can only be saved if D. comes up with some really really surprising and unexpected move. But we're on wikipedia, and our opinions don't matter. Just because we personally think the proof is dead doesn't mean we have to write the article to reflect this point of view. "Can I ask what it will take to get you to say 'it's over'," Me personally, I think that it is never over. If there is some valid proof at all, then for any invalid proof there is also some finite sequence of changes that transforms it into this valid one, and even going completely random steps might eventually coincide with one of those sequences. So it is the wrong thing to even ask such questions completely outside of the realm of computer science as "is it over"? If you want to know exactly, I am a Popperian, and I think that Proofs and Refutations makes quite some important points (though I don't want to say I like any of the other works Lakatos has written). But all that is quite irrelevant for the question what to put into this article and I think the whole discussion will be obsolete once things develop, so perhaps let's just wait and see what comes next (and not speculate on what might come next -- as you do -- and try to to anticipate it in the article). BTW, everyone with their rather hostile attitude towards D. seems to forget that it wasn't D. who put this proof on the public web and that his initial announcement wasn't public either. --rtc (talk) 21:40, 18 August 2010 (UTC)

Sorry, I don't think this is working:

• They are not mere "announcements", they are attempts to prove the thing -- they are more than "attempts to prove the thing", they are attempts that have been proclaimed successful by their authors (i.e. announcements) without leading to general recognition of actual success. Most P/NP proof attempts (in fact all of them so far) are unsuccessful, but in the usual situation, the attempter is careful enough to recognize the failure and doesn't proclaim success, so those attempts are not listed in the section. Yet those unsuccessful attempts are generally higher quality work than the erroneously reported "successes". That's why the section title is misleading and there's not really an encyclopedic topic area like "attempted proofs" in the current sense of the article (if you really want to claim otherwise, please cite sources).

  To the extent that there is such a topic as "attempts at proof", it consists of mathematical techniques that were tried and didn't work, not papers that made erroneous claims. See Fortnow's survey article[10] section 4 ("In this section we present a number of ways we have tried and failed to prove P != NP") for what I have in mind. In fact I'd be happy to have a section like that, though "attempts at proof" is still not an ideal title for it. I'd be ok with titling the current section "proposed proofs" instead of "attempts at proof" or "proof announcements" (I always like that use of "proposed") so I'll change it to that unless you've got another suggestion.

• The proof has not yet been sent to a journal and has not been formally peer reviewed in this sense. Don't be unjust. One doesn't accept affirmative arguments if outside of formal journal refereeing as peer review, so one shouldn't accept negative argumments made in such a way as peer review. That argument is fallacious on many levels:
  1. Your proposed symmetry between positive and negative arguments is not how things work in mathematics. We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right. By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals.
  2. In the absence of formal refereeing (which we might never hear the result of even if it does take place) we either don't write about it, or (in cases like this where we sort of have to), we go with the best info we have, which by now is almost all negative. I accept your criticism that my text went too far in making it sound like every last hope for this proof had been extinguished. I'm happy to have it revised, such as by including Lipton's quoting of Yogi Berra. Berra's quote evokes an image of a baseball team that's 20 points behind in the last inning of a game but hasn't yet formally lost, a reasonable depiction (IMO) of the status of D's proof. But your reversion (which eliminated several cited sources) makes it sound like a 50/50 proposition, and it isn't anything like that and never was. The article doesn't neutrally present the views in the available sources.
  3. Formal refereeing doesn't create a final pronouncement either in either the positive or negative direction. In the positive direction, we have a list of published false theorems that were refereed but later found wrong. In the negative direction, Perelman's proof of the Poincaré conjecture was never sent to a journal or formally refereed, but everyone thinks it's right and Perelman was offered (and declined) both the Fields medal and the Millenium prize. I don't mind too much that WP's content about Deolalikar's proof has from the beginning been sourced mostly from research blogs rather than journals, since we've (up to now) used pretty good judgment about what to cite (we've limited the selections to respectable researchers who seem to present the mainstream view). But I find it weird to use such sources one-sidedly, i.e. only when they're favorable to the proof, which is what you seem to be calling for. If we're only going to accept refereed results, we should remove mention of D's paper altogether.
• I do agree about D not seeking publicity for the proof, which is why I worked to get his biography deleted, and I think the paragraph I wrote treated him with dignity. I didn't mention Scott Aaronson's $200K bet against the proof being fixable in the next 8 6 years,[11], or Gasarch's saying D. will stop being a serious researcher if he doesn't fix or withdraw the proof by August 26 (cited above) or Fortnow's remark about a 12 stage process (likewise), or Terence Tao's comparing the reaction to D's proof to the failure of a spam filter[12] or Tao's brutal car analogy[13] or Oded Goldreich's encouraging complexity experts to refuse to even look at proofs like this.[14] But we should take all these things into consideration when assessing how to write the neutral point of view as we are required to. The current version simply doesn't reflect the existing state of affairs.

I'm finding this conversation rather tedious and the current state of the section to be pretty bad. I may attempt another edit that tries to address all the above points (Rtc's and mine), but I wish someone else would weigh in on the discussion. 67.122.209.167 (talk) 02:00, 19 August 2010 (UTC)

I agree that "Notable Attempts at Proof" is a terrible title for the section and is certainly not neutral. I don't see how FLT having been proved makes any difference to coverage of history of a problem, unless there's now a WP:LogicalPostivism. :-) MSGJ said above "Just because not everything is known about a topic is not a reason to exclude what is known" which is exactly what I was trying to express, thank you.

Think we should include "progressive and/or notable papers submitted in relation to the problem whether right or wrong" but I'm struggling to make that encyclopaedic. The challenge with D's paper is that it hasn't been around long enough for an NPOV summary of milestones that moved us closer to a proof, even if the final paper fails as an entire proof.

Thus any mention of D should be restricted to "he's released a paper, there's widespread criticism of certain aspects, but no consensus yet. It has not been withdrawn at the time of writing. See your favourite complexity blog for latest." The current version of the article does that well.

I have had a look at a couple of survey papers and a SHORT summary of those kinds of activities definitely belongs in this article - just not sure where.Infojunkie23 (talk) 10:15, 19 August 2010 (UTC)

"they are more than "attempts to prove the thing", they are attempts that have been proclaimed successful by their authors (i.e. announcements) without leading to general recognition of actual success" Sure, then we agree. What about "claimed proofs"?

"Your proposed symmetry between positive and negative arguments is not how things work in mathematics. We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right. By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals." My symmetry argument was talking about what to consider as peer review and what not to consider peer review. It was not about assuming something to be wrong or right. Please read more carefully what I write. With respect to "how things work in mathematics[:] We do indeed assume (asymmetrically) that any proposed solution to a major open problem (like D's) is wrong until we start hearing knowledgeable people say they think it is right." I can only say that this attitude is missing the point of mathematics entirely, which is not about belief in the truth of theorems or validity proofs, but about the quite entirely different activity of finding true theorems and valid proofs. People often confuse these two things, unfortunately and incorrectly assume that questions about if people should believe in it or not have anything do with mathematics. "which we might never hear the result of even if it does take place" again, we don't need to speculate. "By your logic, the dozens of "proofs" in Woeginger's list should also be treated as potentially valid because they haven't been formally rejected by journals." They should be treated as not having undergone peer reviewed. That was all what I said. "Formal refereeing doesn't create a final pronouncement either in either the positive or negative direction." Again, I did not claim that. But at least it creates a judgment that that can then be mentioned in the article. "In the positive direction, we have a list of published false theorems that were refereed but later found wrong. In the negative direction, Perelman's proof of the Poincaré conjecture was never sent to a journal or formally refereed, but everyone thinks it's right and Perelman was offered (and declined) both the Fields medal and the Millenium prize." As I said, I didn't say anything like this. "But I find it weird to use such sources one-sidedly, i.e. only when they're favorable to the proof, which is what you seem to be calling for." Certainly not... I merely criticized the use of vague statements like "consensus emerged". I'm sure you are overestimating the differences of our views on what the article should look like. --rtc (talk) 14:44, 19 August 2010 (UTC)

I changed the section title to "claimed solutions", which I hope works for you. The current text is better than what was there before, though still not ideal. "Consensus emerged" is not vague and precisely describes the current situation, per numerous sources in addition to the NYT article whose citation you removed[15]: John Pavlus, Technology Review "the current consensus is that Deolalikar's approach is fundamentally flawed."[16]; Scott Aaronson, "a clear consensus has emerged that the proof, as it stands, is fatally flawed."[17]; and of course Dick Lipton, "the consensus seems to be best summarized by a recent comment here by Terence Tao"[18]. That comment was also called "magisterial" by Scott Aaronson.[19] Tao later downgraded his estimate to "no, no, and probably not",[20] and later still, "I think that the public scrutiny phase of this ms has basically been concluded."[21] Leo Gomes of Forbes magazine doesn't use the word "consensus" but says "now, the conventional wisdom is nowhere near as generous" [compared to initiallly] and describes another Tao comment as a "bitch slap".[22] Seema Singh of Mint (Indian financial newspaper affiliated with Wall Street Journal) says "computer scientists in India, fed up of their countrymen staking claims to answers as profound as P equals NP... have come together in refuting such assertions."[23] I could keep going, but what more do you want? The Mint article is pretty good and includes a discussion with Manindra Agrawal of AKS primality test fame, if that's of interest. 67.122.209.167 (talk) 01:59, 21 August 2010 (UTC)

Actually the current version[24] is pretty harsh and should be softened. 67.122.209.167 (talk) 03:42, 21 August 2010 (UTC)

further reading, references, etc.

Why is Berlekamp and Wolfe's book on Go in the "further reading" section? I remember looking at it and finding it interesting, but don't see what it has to do with the P vs NP problem. As I remember, n-by-n Go is PSPACE-complete and therefore probably outside NP.

Some other books mentioned, and some parts of the article, are about NP-completeness in general, rather than about the P vs NP problem specifically. We have a separate article about NP-completeness. Should we merge this article?

I notice that the references to the Millenium prize have been removed, except for the big template. Is that intentional? It was previously mentioned rather prominently in the article intro, which has since been re-written. I think it should at least be mentioned someplace in the article, though I could be convinced that the old version gave it too much emphasis by featuring it so prominently in the lead. 67.122.209.167 (talk) 22:44, 21 August 2010 (UTC)

I removed the Berlekamp/Wolfe book and added one by Goldreich which is more on-subject and which has drafts online. 67.117.146.38 (new address again) (talk) 08:08, 26 August 2010 (UTC)

Numerical analysis approaches?

NP problems can be translated into continuous problems - with constrains, or even just finding minimum of nonnegative polynomial. It's going out of standard combinatorial picture into numerical analysis and working literally between solutions - even finding complexity of such gradient method seams extremely difficult - it makes searching for P!=NP proof a bit hopeless. What is the status of such approaches? I couldn't find any information about it on Wikipedia - maybe it should be mentioned? —Preceding unsigned comment added by 195.43.85.90 (talk) 07:56, 23 August 2010 (UTC)

That kind of thing doesn't work so well for hard combinatorial optimization problems if that's what you're asking. Or, there is an analogous (and still open) P vs NP problem in real computation, if that's what you're asking about. The Blum-Cucker-Shub-Smale book listed in that article is excellent. 67.122.209.167 (talk) 11:37, 23 August 2010 (UTC)

I should add, there were a bunch of papers by Ted Swart in the 1980's claiming to have encoded Hamiltonian Path as a linear programming problem (solvable in polynomial time in the # of variables), thus proving P=NP. The error was that the number of required LP variables is exponential in the original problem size (proved by Yannakakis). The saga is mentioned in Woeginger's P vs NP page mentioned in the article. 67.122.209.167 (talk) 11:41, 23 August 2010 (UTC)

I've seen this Blum-Cucker-Shub-Smale book a few years ago - it's about something different: consequences of theoretical possibility of computing on real numbers. As I remember it's rather about computability and practically doesn't touch complexity. About linear programming approach - it requires huge amount of controllable constrains, but we can do it much simpler - translate it into just finding minimum of low degree real nonnegative polynomial (of linear number of variables) - just a single polynomial without any constrains (no exponential number of LP variables). For example for 3-SAT:

$((x-1)^{2}+y^{2})((x-1)^{2}+(y-1)^{2})(x^{2}+(y-1)^{2})$ as (x OR y) and analogously 7 terms for triples - their sum reaches zero iff all terms are fulfilled.

Reaching local minimals should be quick - the only source of exponential complexity could be huge number of local minimas(???)195.43.85.90 (talk) 12:26, 23 August 2010 (UTC)

... but in local minimals gradient vector has all coordinates (also polynomials) zero - there is polynomially large number of such points. Gradient method for polynomials should have polynomial convergence time (??) ... where exponential complexity could come from? 195.43.85.90 (talk) 13:13, 23 August 2010 (UTC)

That doesn't sound right. When you multiply all that out, you get something of very high degree in a lot of variables and I don't see how to move around between minima or why there should be polynomially many. Simulated annealing makes some random jumps that can help in physically-inspired problems but not very hard ones that arise in (say) cryptography. I think cryptographers were dealing with this kind of attack long before P/NP was on anyone's mind. 67.117.145.46 (talk) 14:08, 23 August 2010 (UTC)

We don't multiply them, but just sum up - sum of nonnegative polynomials is zero iff all of them are zero. About simulated annealing - yes, in this form there are availible many advanced methods far from standard combinatorial picture, eventual P!=NP proof would have to consider ... but I still don't know how simple gradient method could be exponential? 195.43.85.90 (talk) 14:32, 23 August 2010 (UTC)

Hmm, maybe you're right about summing (I was thinking of a different encoding where each AND input means a multiplication). But gradient method iirc means pick a starting point, then follow gradient to a local minimum, and you probably have to check from exponentially many starting points to make sure you find all the minima. Anyway this is the wrong place for this discussion (we're only supposed to be talking about how to improve the article). It's better to ask this kind of thing at the mathematics reference desk, wp:RDMA. 67.117.145.46 (talk) 18:47, 23 August 2010 (UTC)

Gradient vector of polynomial is also made of polynomials - it cannot be zero too often - there are at most polynomial number of local minimas. And I agree it's not a place for such discussions, I only wanted to point out that there are also completely qualitatively different approaches than standard combinatorial ones and maybe it should be mentioned in the article. Cheers 195.43.85.90 (talk) 19:36, 23 August 2010 (UTC)

Yes, it might be worth looking in some optimization book and mentioning a method or two, the existence of approximation methods for problems like TSP, etc. I think in practice, heuristic SAT algorithms like DPLL don't use numerics like this. Re the gradient method, one issue is you might pick starting points A,B,C and they all lead to the same local minimum. How many tries do you have to make (and where?) before you know you have found the global minimum? Sounds like exponential. 67.117.145.46 (talk) 20:13, 23 August 2010 (UTC)

If the number of local minimums can be bounded by polynomially large number, we can extend this problem to search simultaneously for this number of 'repelling' local minimums: minimize "sum of polynomial value for each set" - "sum of squares of distances for each pair of sets". In this extended problem the degree of polynomial is unchanged and the number of variables increased polynomially. Its local minimum should contain a permutation of all local minimums of the original problem. So the exponential complexity would rather need to be somewhere in convergence of gradient methods (???). Standard: discrete approaches like DPLL are completely different - they work on concrete true/false valuations, while in continuous numerical analysis approaches we work literally between them. 195.43.85.90 (talk) 05:01, 24 August 2010 (UTC)

A multivariate polynomial can easily have an exponential number of local minima. For example, $x_{1}^{2}(x_{1}-1)^{2}+x_{2}^{2}(x_{2}-1)^{2}+\cdots +x_{n}^{2}(x_{n}-1)^{2}$, which looks quite similar to the polynomials you consider, has local minimum at each point of the Boolean cube {0,1}ⁿ.—Emil J. 13:29, 24 August 2010 (UTC)

Empty string not handled by "formal" definition

The first paragraph of section P versus NP problem#Formal definitions for P and NP includes "If there is an algorithm ... which is able to produce the correct answer for any input string of length n in at most c·n^k steps, where k and c are constants independent of the input string, then we say that the problem can be solved in polynomial time ...". This definition fails for the empty input string. For the empty string, n=0 but it cannot be accepted in c·0^k=0 time.

If you want to express the idea that the time is in O(n^k) as stated later in the section, then you need to use a different bound. Possibilities include: b+c·n^k, max(b,c·n^k), and c·(1+n)^k. If you are not picky about the value of k, you could also use (b+n)^k. Which one would you-all prefer? JRSpriggs (talk) 12:58, 24 August 2010 (UTC)

It's customary to use n^c + c.—Emil J. 13:03, 24 August 2010 (UTC)

Done. JRSpriggs (talk) 13:56, 24 August 2010 (UTC)

The way big-O notation was explained when I learned it was: a function f is in O(n^k) iff there exists M,c such that for every n>M, we have f(n) < c·n^k. That is, we care about the asymptotic (n→∞) situation, not small values of n. Isn't that the way it's always done now? 71.141.91.119 (talk) 21:23, 24 August 2010 (UTC)

Yes, but the sentence talks about all values of n (length of the string). Excluding small values would be the same as using max(b,c·n^k) where b is an upper-bound on the time required to process the finite number of short strings, i.e. strings with n≤M. JRSpriggs (talk) 22:02, 24 August 2010 (UTC)

If the running time is in O(n^k) then the sentence as written is obviously true. 67.117.146.38 (talk) 02:25, 25 August 2010 (UTC)

There is no O in the sentence as written. The sentence claimed the running time to be c·n^k, not O(n^k), and as such it was wrong. Obviously, it is written in this way in order to avoid the big-O notation for the benefit of readers who are not familiar with it.—Emil J. 09:51, 25 August 2010 (UTC)

Narendra Chaudhari and links

I'm not sure why Professor Chaudhari's claimed proof is any more notable than others named in Woeginger's list. As for the links to http://dcis.uohyd.ernet.in, they seem to be intermittent, at least from the US. They're live for me at the moment. However,

• The second reference, ^[23], is a clear copyright violation; it has a handwritten note:

  © Indian Academy of Mathematics

  Copy for private use only.

• The third reference, ^[24], has pointers to ^[23] and to lecture notes. Perhaps usable as an external link, but certainly not a reference.

I should remove the copyright violation, but I don't want to edit war, and I've made 3 reverts "today" (in the past 24 hours). — Arthur Rubin (talk) 16:35, 6 September 2010 (UTC)

Posting a link to external page is not a copyright violation. There is a link to it from the seminar page. In any case, it is clear that the paper was published in a peer reviewed journal - that is notable enough. Ckplato (talk)

I agree with your analysis. As for notability, I also have doubts, though the fact that he actually managed to get it published does have some significance.—Emil J. 16:49, 6 September 2010 (UTC)

This paper seems dubious. I've left a possibly-relevant note on David Eppstein's user talk. 75.57.241.73 (talk) 09:11, 8 September 2010 (UTC)

Regarding this, it turns out that the edits by Rjlipton (talk · contribs) are not actually by R. J. Lipton. I've blocked the account for violating our username policy. —David Eppstein (talk) 16:44, 8 September 2010 (UTC)

Unlike the recent attempt, this attempt received no coverage from experts (or the blogosphere). This seems no more notable than any of those 50+ proofs in Woeginger's list. --Robin (talk) 14:48, 8 September 2010 (UTC)

Why is blog more important than publishing in a peer review journal? Aren't you biased - is it your POV that Indian journals and IIT amount to nothing. The article should have this info, and it does not claim that the proof is true, but the paper got through peer review and this carries some weight. Ckplato (talk)

Yeah, it's been reverted already, which is good. 75.57.241.73 (talk) 20:16, 8 September 2010 (UTC)

The paper is peer reviewed and published. This is what makes it different from all the articles on the list, including Deolalikar. Presently, there is bias towards Deolalikar attempt - either both should be omitted, or both kept. Peer review is certainly a distinguishing feature, and the author is notable professor at very notable IIT. The paper might be wrong (wrong results occasionally get published), but the publishing in a peer reviewed article of a major Indian mathematical journal is reason enough to include it. If it is proven to be wrong, as it is a reasonable possibility, that still is a serious incident that it got through peer review, and should be mentioned. Ckplato (talk) 16:56, 9 September 2010 (UTC)

I'd just like to point out the factual inaccuracy with calling IIT Indore a "very notable IIT." IIT Indore was started last year. It is barely functional, let alone "very notable." --Robin (talk) 20:40, 10 September 2010 (UTC)

See also here. 67.117.146.236 (talk) 07:15, 14 September 2010 (UTC)

Bias which favors Deolalikar

There are few (I found only one) articles that are peer reviewed and claim solution to P vs NP. Almost all other (on the list of over 60) are published in archive, which is not peer reviewed. If there are other peer reviewed articles, they should be mentioned, but there do not seem to be any (peer review is a filter, but this one slipped through). This is notable - peer reviewed publication of a major solution to a problem is a significant event, even if it in the end turns out to be error in the paper. It is POV to put more weight to Deolalikar than to a paper that has already passed peer review - by Clay Institute criteria, paper needs to be published in peer reviewed journal first, and second, to survive two years of scrutiny after publication. Deolalikar didn't even publish the paper. Are you arbitrarily assigning importance that ignores what happens in India - IIT is known to produce results such as PRIMES in P, so it is something that should be noted. India has scientific community that counts too. Would you argue that Indian released films in Bollywood should not be mentioned, because only Hollywood counts as wikipedia worthy? If something is ignored by Western media, it does not mean it doesn't exist. Ckplato (talk) 17:19, 9 September 2010 (UTC)

We mentioned Deolalikar because of the amount attention his proof received from experts and the public, as discussed in the AfD. Take a look at the Polymath wiki page about it (linked from the footnote after "reviewed by academics" or some such) for more citations. The Chaudhury proof has gotten no traction at all and looks pretty hopeless. In the (unlikely) event that some recognized complexity experts start saying they think it's right, we should mention it in the article. The current situation is that it went into a relatively obscure general math journal without much evidence of having been refereed by complexity specialists (that would be the standard of "peer review" for something like this, I think) so it's not especially remarkable. Anyway, I don't think mentioning Deolalikar "favors" him, since it's not exactly a "favor" to have Wikipedia say about the poor guy basically that he caused a big uproar by announcing a proof that turned out to be wrong. Regarding the AKS proof, you might look at the Mint article where they interviewed Agrawal about the Deolalikar proof.[25] The audio of the interview is linked to that article and it's also interesting. Note there are plenty of absolutely first-class Indian complexity researchers including Agrawal, Arora, the Vaziranis, etc. But the article also indicates a tendency of some others to overclaim. 75.57.241.73 (talk) 18:43, 9 September 2010 (UTC)

Deolalikar's proof is correct. Richard J. Lipton (talk) 00:31, 14 October 2010 (UTC)

Given our previous issues with Rjlipton (talk · contribs) (who was definitely not Richard J. Lipton) I would like to see some evidence that this new user with a single and rather surprising edit is actually Richard J. Lipton. In the meantime I have blocked him/her in order to protect the identity of the real Richard J. Lipton. —David Eppstein (talk) 03:59, 14 October 2010 (UTC)

Lol Richard Eppstein (talk) 05:36, 14 October 2010 (UTC)

Just smurfing David Lipton (talk) 05:38, 14 October 2010 (UTC)

Lead section

Thanks to all those who have obviously made an effort to make the introduction to this article (probably as far as many of us will read) accessible to ordinary readers. Many times in Wikipedia maths articles we don't see this (though I appreciate the difficulties involved). I have one suggestion. On reading the introduction, the feeling I'm left with is "intuitively, this seems obviously untrue; why would it be such an important problem?". I wonder if it might be worth adding something to the effect that "although it is widely believed that P ≠ NP, the problem's importance stems from the current lack of proof, given the potentially dramatic consequences of the opposite result". —Preceding unsigned comment added by 86.173.35.126 (talk) 13:52, 23 September 2010 (UTC)

I'll try giving a partial medical analogy (not usable in article of course). Imagine 14th-century doctors knew about many intractable (i.e. fatal) diseases, like malaria, pneumonia, bubonic plague, etc, including one I'll call "3-satulosis". They had drastic treatments for these diseases that were at best better than nothing. There was another disease called "2-satulosis" with very similar symptoms to 3-satulosis, which responded to conventional treatment in about the same way (i.e. usually fatal). But they somehow found miraculously that 2-satulosis could be completely cured by just combing the person's hair the right way (i.e. 2SAT is in P). Could malaria, plague, etc. also be cured by such simple means (i.e. P=NP)? Almost certainly not. So why was 2-satulosis different? Was it possible that all those dread diseases had comparably trivial cures? Most doctors thought the answer was no, and that malaria, plague, etc. had a unifying explanation called "germs". But nobody could prove that until the 1600's when centuries of incremental improvements in eyeglasses and optics led to the invention of the microscope, and it became possible to actually see the germs. (It also determined that 2-satulosis was caused by, uh, follicle stress rather than infection.) The microscope created vastly improved understanding of diseases, medicine, and biology in general.

Back to P vs NP. Nobody has much hope that 3SAT (etc.) are in P, but what is the real cause of intractability in that case? The interest in the P vs NP problem is not merely to find out the answer. It is based on an expectation formed by decades of incremental improvements, that the person who solves it is going to have to do so by inventing the equivalent of the microscope, which will expand our knowledge in all sorts of ways we can't currently predict. Right now we feel like we're stuck in the 14th century, where things that are perfectly obvious (P!=NP) are nonetheless beyond our mathematical grasp. There is incredibly important stuff right under our noses, but we don't have the tools to see it clearly. We don't even know that P!=PSPACE or that SAT can't be solved in linear time, much less polynomial time. And it's frustrating and maddening. So of course there is a sense of importance around the problem.

Of course to complete the analogy, the medieval doctors would have to learn how to convert one dread disease (DD) into another, showing that 3-satulosis was a DD-complete illness so that if it could be cured at all, they could all the DD's could be cured with one drug (with no hint as to what the drug might be).... but we won't go that far. Thanks, try the veal, and I'm here til Friday ;-). 69.111.192.233 (talk) 09:00, 19 November 2010 (UTC)

I'm not very experienced with editing wikipedia, but can someone fix the diagram in the lead section? Currently it shows "Diagram of complexity classes provided that P ≠ NP." which is an interesting claim, since it shows P to not be a subset of NP. — Preceding unsigned comment added by Joelmiller (talk • contribs) 19:50, 23 February 2011 (UTC)

The diagram looks fine to me. It shows P (an elliptical blob) sitting inside of NP (the rectangular region surrounding both P and the other elliptical blob). The other elliptical blob is NPC, the NP-complete problems, and if P != NP then NPC is disjoint from P, as the diagram shows. The main thing the diagram is trying to show is that if P != NP, then there are problems that are outside of P but that are not NP-hard. For example, integer factoring is a likely candidate for being such a problem. 71.141.88.54 (talk) 21:19, 28 February 2011 (UTC)

Example

Something seems not right with the example given in section Context. It defines a set of integers, and claims that this set is an element of a set of decision problems! And it introduces a set R which actually is isomorphic to COMPOSITE but doesn't make further reference of it. I'm ignoring that the symbol N is not in blackboard letters. Nageh (talk) 17:30, 9 November 2010 (UTC)

Decision problems being sets of natural numbers is a standard definition, see decision problem. The R business refers to its usage in the definition in the section "Formal definitions for P and NP", where I've moved the example.—Emil J. 17:52, 9 November 2010 (UTC)

Thanks, Emil! Nageh (talk) 17:55, 9 November 2010 (UTC)

Slashdot

Slashdot is not a self published site and passes wp:verifiability. If you're going to remove a cited point please do it on logical grounds, not by calling a news site "non-mainstream". Best, Markvs88 (talk) 20:19, 20 January 2011 (UTC)

The article in question [26] attributes the news to "an anonymous reader". Even if Slashdot counts as a "reliable source", all that it's "reliably" reporting is that some anonymous reader, somewhere, claims he heard something--and while I'm sure that's true, it isn't notable. So this news should wait until it's actually reported with names attached. If Romanov really has released this finding, it'll be reported somewhere soon enough, as something other than hearsay. -- Narsil (talk) 20:25, 20 January 2011 (UTC)

Please read up on the notability guideline. Nageh (talk) 20:27, 20 January 2011 (UTC)

Shenanigans. Only one point in the "Solutions" section has multiple citations, and the Slashdot article lead was done by an anonymous poster, the article was published by CmdrTaco and has links to not only the Wikipeida 3-SAT article, but to the source code and the original article... did you click on [[27]] (at Cornell University Libary)?? BTW: the 3RR warning is void, as this is the first reply I've gotten to talk. Best, Markvs88 (talk) 20:32, 20 January 2011 (UTC)

Leaving the other issues aside--you don't need to start a conversation on the talk page to get the "3-revert" clock ticking. If you make a fourth revision to the article today, as I understand it, you will be in violation of WP:3RR (especially given that I count at least four editors who think the paragraph should be taken out--me, Nageh, David Eppstein, and Justin W Smith). We should let this cool off for a day. -- Narsil (talk) 20:39, 20 January 2011 (UTC)

That would be true, but I claim expection as I'm reverting obvious vandalism -- this is a valid source that is being removed by editors that should know enough to read wp:own. Now, if someone would be so kind as to answer these two questions, we can continue as civilized people?

• Explain WHY a citation from the NYT is valid but /. is not, if the source has to be "mainstream" or "mainstream for theoretical CS".
• Explain WHY this one point needs multiple sources, when the rest of the "Claimed Solutions" section lacks them?

Best, Markvs88 (talk) 20:49, 20 January 2011 (UTC)

Good-faith contents disputes are never vandalism, and claiming they are as an excuse to blow past 3RR is more likely to get you blocked, not less. By the way, you can add me to the list of editors who does not wish to see this here without much more substantial coverage. I did not revert you because I was busy reading up on the proposed proof, but I would have reverted you for the same good-faith reason that others did - there is as yet no evidence that this is of any significance. — Gavia immer (talk) 20:54, 20 January 2011 (UTC)

Good faith means exactly that... and I'm pointing out that this mass delete-fest is not in good faith. Specifically, the section needs to either allow the point to stand or delete the section as wp:verifiability either succeeds or fails. Best, Markvs88 (talk) 21:02, 20 January 2011 (UTC)

It should be noted that while the arXiv site is maintained and operated by the Cornell University Library, it is a self-publication site for registered authors. To quote from the arXiv Goals and Mission [[28]], "It is important to note, however, that arXiv is not a repository for otherwise unpublishable material, nor is it a refereed publication venue." Mlwilson (talk) 20:52, 20 January 2011 (UTC)

That's a fair point. How is that any different from [:http://rjlipton.wordpress.com/2010/09/15/an-update-on-vinay-deolalikars-proof/], which is cited in that same section? It seems to me that the ruler is not being applied equally since Wordpress is a blog site. Best, Markvs88 (talk) 20:59, 20 January 2011 (UTC)

It's a personal blog by an individual who is verifiably an expert in complexity theory, with comments by another individual (Terry Tao) who is also an expert in that field, and our sourcing policies explicitly permit that sort of blog just as they permit other sorts of personal publications by experts. An anonymous Slashdot submission is much lower quality sourcing. — Gavia immer (talk) 21:05, 20 January 2011 (UTC)

Again, Cornell University Libary http://arxiv.org/abs/1011.3944 is not anonymous, and the article was vetted by Cmdrtaco. Really! How does that square with wp:blogs? Can you point me to what "our sourcing policies" means? Or, are you are referring to wp blogs? Thanks, Markvs88 (talk) 21:14, 20 January 2011 (UTC)

I don't think that the reliability of slashdot is the problem here. The fact of the claim is reasonably well substantiated. I think it currently lacks notability. However, this is all a tempest in a teacup. The news is spreading fast, and already more than a dozen sites are echoing the slashdot post. It'll reach plenty of mainstream news sites within 24 hours. In the meantime, wikipedia is an encyclopedia, not a news site, so we can afford to wait. Mlwilson (talk) 21:17, 20 January 2011 (UTC)

So, you favor deleting the entire "Claimed Solutions" section then? Because those blog entries also aren't news and we can afford to wait before posting them. Best, Markvs88 (talk) 21:54, 20 January 2011 (UTC)

Of course not, particularly given that not all of the citations are blogs (two are NYTimes), and many of those blogs are covered under the "recognized expert" exemption. But that's not relevant to the reasons why I haven't pushed to add the latest claim. I'm concerned with notability, not reliability. Woeginger's list currently has 67 P/NP claims; should we include them all? Is there a compelling reason why Wikipedia really needs this particular claim right now? Mlwilson (talk) 22:06, 20 January 2011 (UTC)

I appreciate your not questioning the reliability of /. It's nice to see someone finaly admit that. As to the compelling reason: is there one why it doesn't? Why is P versus NP problem special vs. (say) Joe Lieberman? Oh well, I guess no one is actually going to bother actually answering my questions above, so I'll just go back to "lurking" on this page as I've (mostly) been doing for months. Done, Markvs88 (talk) 22:18, 20 January 2011 (UTC)

There are two definitions of reliability here. One is trustworthiness as a secondary, journalistic source. In the specific case, you may consider /. reliable. The other definition is that of expertise. The opinion of an expert on the field of theoretical CS may be considered reliable and/or notable whereas that of a layman certainly is not. The issue in this case, as I pointed out further below, is that we do neither have significant coverage by reliable (i.e., trustworthy) secondary sources nor published opinions by independent experts who indicate the proof's notability. Nageh (talk) 22:40, 20 January 2011 (UTC)

Hi all, I would like to add my opinion wrt the comment by Daniel Eppstein, that we should wait until a peer reviewed article appears. The purported solution is in the claimed proofs section of the article. One expects that all of the claimed proofs will be proven false under close inspection, i.e. once they pass the usual peer review cycle, until one comes up with the correct solution. As long as it is in the claimed proofs section, I think that it is not necessary for the work to be published in a peer reviewed journal. After all, the reason that we have this section in the first place, is that this is one of the most important unsolved problems in CS today and many people eagerly await the latest attempt to solve it. Gakrivas (talk) 21:27, 20 January 2011 (UTC)

"Daniel"??? —David Eppstein (talk) 23:27, 20 January 2011 (UTC)

Oooops, sorry David...Gakrivas (talk) 10:12, 21 January 2011 (UTC)

Peer review is not a criteria for citation. Best, Markvs88 (talk) 21:52, 20 January 2011 (UTC)

In general a "claimed proof" is not notable and should not be listed. (I'm sure there have been hundreds of them.) On rare occasions a claim gets "significant coverage" (for whatever reason). It's only these rare instances, that should (potentially) be mentioned in this article. Wikipedia:NOTABLE makes this quite clear; Slashdot alone is not enough. Deolalikar's claim did receive such attention, which is why it is included. Personally, I think the "Claimed solutions" section should be removed altogether. Justin W Smith ^talk/_stalk 22:03, 20 January 2011 (UTC)

As do I. Deolalikar's attempted proof was the focus of Internet attention, briefly, but it has been shown to have serious flaws. Keeping the mention of Deolalikar just because he got some attention once is serious recentism. Having said that, the present matter is not even in the same class as Deolalikar's attempt. Until it gets comparable attention - not just a Slashdot posting - there's surely no reason to have it here even if you believe Deolalikar's attempt does belong. — Gavia immer (talk) 22:10, 20 January 2011 (UTC)

(edit conflict)For the moment the claimed proof neither has received significant coverage by reliable independent secondary sources nor scrutiny by experts on the subject. Deolalikar's claimed proof received significant coverage by media worldwide, and was noted as a serious attempt by experts. Now the same may happen for this new claimed proof, in which case notability will be given – or it may not, in which case it will all have been a big fuzz. So, we'll wait. (And yes, I'm also somewhat hesitant about including claimed proofs at all.) Nageh (talk) 22:28, 20 January 2011 (UTC)

I read some of the discussion on Slashdot. It seems that although there is a published algorithm with source code, the author does not claim to prove that it has polynomial complexity, only that he has somehow measured it to be polynomial. I think that the proof is not notable as it is. As for a claimed solutions section, which some editors disagree with, in my opinion they should be kept, but only in the most "notable" unsolved problems, such as Fermat's theorem (now solved), and certainly the N vs NP problem.Gakrivas (talk) 10:12, 21 January 2011 (UTC)

FWIW, complexity theorist Lance Fortnow writes dismissively on twitter about why he hasn't made a full blog post about this one: "when there's a legit approach to PvNP I'll make sure you know about it". —David Eppstein (talk) 16:26, 21 January 2011 (UTC)

Does an efficient solution to 3-SAT really break crypto?

I have some concerns about Nageh's recent edits to the "Consequences of proof" section (though I haven't looked at it recently — could be that what was there before was equally or more problematic).

My concern is that the claim that an efficient solution to 3-SAT would break public-key crypto in general, and symmetric cyphers like AES and 3DES, might be true, but it is not obvious. What you would know from what most people know is that there is a polynomial-time reduction from those problems (appropriately formulated) to 3-SAT. But if the reduction is, say, O(n⁶), then even if the 3-SAT solver itself is highly efficient and practical, it doesn't follow that the solutions to the crypto problems are practical.

I'm not an expert on this, and for all I know, Nageh might be, but in that case I invite him to elaborate more. --Trovatore (talk) 01:08, 11 March 2011 (UTC)

Here are some handwaving reductions, accurate to an order of magnitude or so:

Factoring will directly break the most common public-key crypto, and the reduction from factoring to 3-SAT is very direct. To factor an N bit number, you build a multiplier out of O(N^2) two input gates, using the traditional multiplication algorithm taught in grade school. Each gate corresponds to a single 3-SAT constraint. Then you ask for any assignment of input bits (except those that represent 1 or N) that gives the product you want. If there is a solution then it's the factorization. So an O(N^2) solution to 3-SAT would give you 10^12 operations or so to factor a 1000 bit number, or a few minutes. O(N^3) 3-sat would require 10^18 operations, about 30 years on a uni-processor or about 2 weeks on a 1000 processor system, if it parallelizes. O(N^4) and up for SAT start not helping much, unless the constant is really low.

DES and 3DES are even easier. You build a hardware implementation (a few 10s of thousands of gates) example here, and again each gate corresponds to a 3-sat constraint (plus a small factor for more complex gates, etc.) so maybe 100,000 constraints in all. Then you present a known block, and ask for the key that generates the known result. So an O(N^2) 3-sat give you 10^10 operations, or just seconds. O(N^3) gives you 10^15 operations, or 1,000,000 seconds on a GHz processor, or about 10 days. O(N^4) 3-SAT still works with massive compute power, and O(N^5) and up starts being hard. LouScheffer (talk) 01:49, 11 March 2011 (UTC)

As Lou notes, there are known reductions that aren't really too complex in this case. Even if there weren't, this is basically already covered by Cobham's thesis and the section P versus NP problem#Does_P_mean_.22easy.22.3F. Dcoetzee 01:51, 11 March 2011 (UTC)

Well, Cobham's thesis, taken literally, is obviously wrong. I have to suppose that it is not meant to be taken that literally. Lou Scheffer's remarks are directly responsive, though. --Trovatore (talk) 03:06, 11 March 2011 (UTC)

Well, yes and no. In principle, all that is required is that a problem be harder for an adversary than for a legitimate party. This may just be by a constant factor (in the exponent); see for example Merkle's Puzzles, which was devised before public-key cryptography was invented (or became known to the public). However, should cryptosystems become breakable by polynomial-time algorithms security will be fragile at best, while key sizes, signature sizes, and computing times may become extraordinarily large. To see why this is the case consider this example: Current state in cryptography considers 80-bit symmetric key sizes to be brute force breakable by large (intelligence) organizations within a matter of months. This means that 2^80 (or 2^79) symmetric-key operations can be carried out in that time. Integer multiplications used in public-key cryptography have a bit complexity of O(n^2) in practice, and can be estimated being faster by a factor of 10^-4 per bit compared to symmetric-key operations (e.g., 1000-bit integer multiplication is approx. 100 times slower than a symmetric-key operation). Now the question is: How long do key sizes have to be to maintain the same level of security when an integer factorization algorithm exists with a complexity of O(n^3), O(n^5), or O(n^10)? Ignoring constants, the answers are 2 Gbit, 400 Mbit, and 1000 bits. So there must be a significant gap in the complexity of computation between legitimate party and adversary for the systems to remain practical. (Side note: For a key size of 1000 bits the GNFS with a subexponential complexity is faster than the O(n^10) algorithm, ignoring constants for the latter.) But there is a worry: when there is an integer factorization algorithm that takes O(n^10), who guarantees that none will soon be found with a lower complexity? Cf. AKS primality test.

The second concern with polynomial-time solutions is that according to Moore's law processing power doubles approx. every 18 months, i.e., exponential growth. So you'd have to take this into account, which may considerably degrade performance for legitimate users.

In summary, Cobham's thesis can be considered a guideline, and while an efficient polynomial-time algorithm for 3SAT may not mean an immediate death to current computationally-secure algorithms it will definitely mean a serious injury. To be on the safe side then, it would probably be more wise to switch to information-theoretically secure systems where possible (though public-key encryption cannot be salvaged). Nageh (talk) 12:49, 11 March 2011 (UTC)

PS: You may interpret "efficient solution" in the article as having complexity with no large constants involved. I think the issue of large constants is addressed in the paragraph directly above and in the "Does P mean easy?" section. Nageh (talk) 13:11, 11 March 2011 (UTC)

Yes, but the answer to "does P mean easy?" is just simply "no". The article should not be written assuming otherwise. I'm not saying that you did that; your and Lou Scheffer's answers are satisfactory. But they were necessary. --Trovatore (talk) 20:21, 11 March 2011 (UTC)

Trovatore, you might like Russ Impagliazzo's "Five Worlds" paper[29] on average-case complexity, that we should probably cite in the article. 75.57.242.120 (talk) 16:37, 18 March 2011 (UTC)

I'm not suggesting that Cobham's thesis resolves the question - what I am suggesting is that the question of whether a polynomial time algorithm (for factorization or anything else) would be efficient in practice is exactly what all the discussion in Cobham's thesis is about. There is little need to duplicate here. Dcoetzee 17:51, 18 March 2011 (UTC)

My point is still that the article should not be written assuming that such an algorithm would be efficient in practice. It doesn't have to replicate the discussion of Cobham's thesis; it just shouldn't assume the thesis is true. --Trovatore (talk) 18:02, 18 March 2011 (UTC)

I added a cite to the Five Worlds paper, which describes some of the possible range of consequences. Maybe that can help a little. 75.57.242.120 (talk) 09:29, 19 March 2011 (UTC)

Although Impagliazzo's Five Worlds are an interesting classification I don't see where you read through that Algorithmica implies approx. linear-time algorithms. In fact, all it says is that P=NP. More importantly, this paper is primarily studying various aspects of average-case complexity, and in this regard is contemplating worlds where NP problems exist but may be "easy" (polynomial-time) in practice (because it is hard to find hard instances) or where hard problems exist but cannot be made to good use (because no one-way functions exist). While I think the paragraph may be a good addition to the article, it is probably not right there as it does not help in understanding the question at hand, which is "Does P mean easy?". Nageh (talk) 16:46, 19 March 2011 (UTC)

You're right about the linear-time thing, I thought I remembered it from the paper but I must have been thinking of something else. I'll fix it. I think the paper is still of some use in understanding the relationship between P/NP and "hard". 75.57.242.120 (talk) 17:58, 19 March 2011 (UTC)

I don't really see how. I only scanned it so I could have missed something. But as far as I can tell, the author more or less assumes that P means easy, which is the point at issue. --Trovatore (talk) 18:11, 19 March 2011 (UTC)

Yep. The paper is even explicit in disregarding constants of poly-time algorithms (introduction of chapter 2). I think the paragraph could make a good addition at the end of section "Consequences of proof". I'm too lazy to integrate it myself, and it requires clarification of the current last paragraph in that section. Wanna go ahead, anonymous? Nageh (talk) 18:25, 19 March 2011 (UTC)

Thanks. I moved it and added an intro sentence, please see if it's ok. 75.57.242.120 (talk) 20:45, 19 March 2011 (UTC)

Stephen Cook's Turing award lecture also has some discussion of this question. I put a link to it at Talk:Cobham's thesis and might try to integrate it into that article. 75.57.242.120 (talk) 01:35, 31 March 2011 (UTC)