Talk:Complexity classes P and NP

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science.
???	This article has not yet received a rating on the assessment scale.
???	This article has not yet received an importance rating on the assessment scale.

This article is within the scope of WikiProject Mathematics.
Mathematics grading:	B+ Class	High Importance	Field: Discrete mathematics
Consider nominating for Good Article status. Tompw 19:38, 7 October 2006 (UTC)

[edit] Old discussion

I'm reluctant to contribute to the Wikipedia and hack someone else's text, but I'd like to point out that prime factorization and NP-completeness don't have anything to do with each other (or at least, nobody to my knowledge has shown that they do). The article gives the misleading impression that if someone were to prove P=NP, cryto-algorithms that rely on the hardness of factorizing prime numbers would be in jeapordy. It would be better, IMO, to stick to propositional SAT to illustrate the difference between P and NP. (as per the article on NP-completeness, which, it seems to me could well be subsumed in the discussion of the two complexity classes.

BTW, I rather disagree that a proof that P = NP would have no practical consequences, but that's another discussion.

- Andre Vellino (vellino@sympatico.ca)

The article mentions factorization only as a simple and hopefully intuitive example of a problem in NP; it also says explicitly that it is unknown whether the problem is in P. The concept of NP-completeness is not introduced until several paragraphs later. So the article does not suggest a connection between factorization and NP-completeness. AxelBoldt

This question was asked on http://www.slashdot.org a little while ago, and it seems relevant here: What, if any, would be the effects of a proof that P=NP, or that P≠NP, or indeed that the question is undecidable?
- Stuart

The latter two wouldn't have any practical consequences, but it would be a big deal in the world of theoretical computer science (and the last also one in logic and mathematics). If somebody proves P=NP, then the practical consequences depend on the way they prove it. If they explicitly exhibit a polynomial algorithm for an NP complete problem, then we would know polynomial algorithms for all NP problems, and if the degrees of the involved polynomials are reasonable, that would be huge news in many fields, but is considered extremely unlikely. It's much more likely that either the polynomial has a ridiculously high degree, or that the proof wouldn't be constructive and just generally concludes P=NP without exhibiting any algorithm altogether. In those two cases, there wouldn't be any immediate practical consequences either. --AxelBoldt

I agree with your conclusion. However, it isn't really possible for there to be a nonconstructive proof of P=NP with no known algorithm. That's because the construction has already been done. I could easily give you an algorithm for, say, Travelling Salesman, whose correctness is obvious, but whose asymptotic running time is unknown. It's easy to prove that if P=NP, then my algorithm is polytime. If anyone ever publishes a "nonconstructive" proof of P=NP, the construction will already exist. This is all academic, of course. The huge multiplicative constant means none of this would have any practical value. --LC

That's very interesting. How does the construction work? --AxelBoldt

Assume the goal is a program that, given a TSP instance, returns the certificate (if "yes") or fails to halt (if "no"). Assume you already have a program to check certificates. Let X=1. Consider the list of all possible programs, sorted first by size, then lexicographically. Run the first X programs for X steps each, with the TSP instance as an input. If any of them halts and returns a certificate, check it. If it's right, halt and return it. If not, continue. If none of them succeed, then increment X, and repeat. Clearly, this algorithm is correct, and its theta running time will be the optimal running time, plus the time to check a certificate. The constant hidden by the theta is exponential in the length of the first program that solves the problem. Totally impractical. I don't remember offhand which books cover this, though I could look it up if needed. It's been a while since I've visited Wikipedia; it's nice to see that it's still going strong. --LC

The description is clear, I don't think we need a reference, but I think it's nice enough to put it in the main article. --AxelBoldt

I've added it, in a form that's hopefully accessible to a wider audience. --LC

Can you also concoct an algorithm which always gives the correct answer in polynomial time? --AxelBoldt

Yes, if you can tell me the running time of the first algorithm (or give a polynomial upper bound for it). Otherwise, I doubt it's possible now. It's too bad that we can construct this algorithm for NP-complete problems, but not for co-NP-complete problems. --LC

But then my original statement stands: if we find a non-constructive proof of P=NP, then we still wouldn't have a polynomial algorithm for NP problems, since a polynomial algorithm has to stop after p(n) steps. --AxelBoldt

I should have said "accept" rather than "solve". Sorry for the confusion. If we could construct a particular algorithm, and prove that it is a polytime algorithm accepting a particular language in NP-complete, then we would have proved P=NP. That would be a constructive proof of P=NP. If we could prove P=NP without knowing any polytime algorithm accepting an NP-complete language, then that would be a nonconstructive proof. The latter is impossible. As soon as someone proves P=NP, we'll immediately know a polytime algorithm that accepts an NP-complete language. It's the algorithm I gave. Note that by the standard definition, an algorithm is a polytime algorithm accepting a language if it returns "YES" in polytime on strings in the language, and never halts on strings outside the language. I'll change the page to say it "accepts the language SUBSET-SUM", rather than "solves the problem SUBSET-SUM". Actually, I think I'll add a second algorithm too. This algorithm (under stronger conditions) yields a stronger result. If there are any algorithms that can be proved to solve (not accept) an NP-complete problem, then this is one of them. I think that's an interesting result too, so I'll write it up later tonight or tomorrow. --LC

From the article:

The integer factorization problem is this: given two natural numbers x and y, with n digits each, decide whether x can be evenly divided by

an integer between 1 and y.

I think the previous example of simply deciding whether a given number is prime was simpler and more intuitive. The main point here is to get the point across that "solving is harder than checking". Was there a reason for changing it? (Also, not both x and y have to have n digits.) AxelBoldt

The problem of finding the best move in Chess or Go (on an n by n board) is EXPTIME-Complete

Is this right? Go has a strictly higher complexity class than Chess. Isn't Go PSPACE-complete and chess is EXPTIME-complete? - anonymous

Go with Ko (Japanese rules) is EXPTIME-complete. Go with other rules might also be EXPTIME-complete, but is only known to be PSPACE-hard. See this, which was also in the references at the bottom of the article. --LC 18:04 Sep 13, 2002 (UTC)

I've also removed this:

It ignores problems that can be well-approximated. There are some NP-complete problems where good approximations can be found quickly.

P and NP and NP-complete only contain decision problems, and you can't approximate a decision problem. Approximations are only possible for problems in classes such as NP-equivalent. --LC 18:11 Sep 13, 2002 (UTC)

What is non-P? This web site says non-P is different from NP. -Jeff

Non-P consists of all those decision problems that cannot be solved in polynomial time. That is indeed very different from NP. AxelBoldt 00:42 Jan 24, 2003 (UTC)

I'm a bit confused regarding NP-complete...is it purely a matter of probability? If P intersected with NPC yields the empty set (for certain) but it is uncertain whether P=NP, either NPC=empty set or P does not equal NP. Am i misunderstanding this?

I'm not sure whether you misunderstand or not. NPC is not the empty set (satisifiability and many other problems are known to be in NPC). So if the intersection of P and NPC is empty, problems in NPC are in NP but not in P. This would imply P!=NP. However, the great unsolved question is whether the intersection of P and NPC is empty or not. If you can prove one way or the other, you'd have solved a [Millennium Prize]] challenge and thus be up for a $1 million USD prize, in due course receive a Turing award and maybe even a Fields medal, get tenure at any university computer science department in the world, possibly have the National Security Agency rather eager to talk to you, and be batting off Hollywood starlets of the appropriate gender wherever you travelled. Well, maybe not the Hollywood starlet part. --Robert Merkel 04:42, 19 Feb 2005 (UTC)

I think the source of the confusion is the following pair of sentences: Theoretical computer scientists currently believe that the relationship among the classes P, NP, and NPC is as shown in the picture. The intersection of P and NPC equals the empty set.

The second sentence comes off as an assertion, when I think the intention was that most comp. scientists believe that. I suggest rewording, something like: Theoretical computer scientists currently believe that the relationship among the classes P, NP, and NPC is as shown in the picture, and that P and NPC are disjoint.

[edit] Quantum computers and NP-hard problems

This statement has recently been added regarding quantum computers: ...none of the problems they are known to be able to solve are NP-hard.

Is this true?

I thought factoring was NP-hard.
Shor's algorithm enables factoring in polynomial time on a quantum computer.
It's even been implemented on a system of (I think) 7 qubits, where it successfully factored the number 15.

So wouldn't that mean that quantum computers are known to be able to solve an NP-hard problem?

RSpeer 22:52, May 6, 2005 (UTC)

Factoring probably isn't NP hard. It's in NP intersect co-NP, which is strictly outside NP-hard provided that NP ≠ coNP, which most people believe is true. Deco 23:58, 6 May 2005 (UTC)

[edit] Small EXPTIME-complete accuracy fix

Before the article stated that EXPTIME-complete problems require exponential time. This is as incorrect as saying that NP-complete problems require nondeterminism to be solved in polynomial time; while this is believed to be true, it need not be (for example, it may be the case that all problems in EXPTIME can actually be solved in O(n^{log n}) time). The reason we know that EXPTIME-complete has no intersection with P is because P is not equal to EXP, which requires a proof by diagonalization and is not at all obvious. Deco 00:32, 8 Jun 2005 (UTC)

[edit] Page of incorrect proofs

I followed the link to the P-versus-NP page, and though its content is fascinating, I'm worried by the author's wording.

Deco is right that this link needs at least a warning that the proofs are incorrect, because the author never bothers to say it. In fact, he says things like "In February 2005, Raju Renjit Grover proved that P is not equal to NP", and on the same page says that other people proved P=NP. Since, last I checked, true is not false and I am not the Queen of England, this must be an unconventional use of the word "prove".

What was the author's motivation for writing like that? Is he being tongue-in-cheek? Is he trying to trip up readers who aren't observant enough to notice that the "proofs" are contradictory? Is he hoping that every reader comes to the conclusion on their own that all the proofs are bunk?

I know the page can't be entirely serious, and I recognize that reading those papers can be a great test of your own skill at finding holes in arguments. But it still alarms me that Wikipedia is linking to false information. A freshman in CS might click quickly through a few links from Wikipedia, not noticing the entirety of the content on that external page, and then go around saying "But I read on Wikipedia that P=NP". That reflects badly on Wikipedia. Or someone might use this link as Wikipedia-endorsed evidence that mathematical logic is flawed.

I don't think stating next to the link that the proofs are incorrect is enough. Is the author of the page contactable? What I'd like to see is a version of the page that keeps all the links to papers, but says more explicitly that the arguments are unlikely to be sound, and does not falsely state that they are proofs.

RSpeer 05:09, Jun 15, 2005 (UTC)

Honestly I found this a bit alarming too. Maybe he's describing them from the author's perspective, or maybe he is being a little playful. Simply creating another version of the page and stealing the list though would be rather dishonest. Maybe we could ask him to make another version of the page for the naive. If you think the link is contentious, though, maybe it's best to remove it. Deco 07:52, 15 Jun 2005 (UTC)

I followed up on this. The page's author told me in e-mail:

I try to formulate all my statements along the statements in the corresponding papers. Whenever I write something like "purportedly proves" or "claims to prove", the authors start pestering me and complaining by email that their proof is correct and not only purportedly correct etc.

He went on to say that it should be evident that they're incorrect, which it pretty much is. Deco 17:54, 30 July 2005 (UTC)

[edit] Oracle discussion

I added a brief discussion of the oracle result regarding the problem. I tried to keep it simple, but if anyone thinks it can be made easier to understand, I welcome your changes. Deco 07:52, 15 Jun 2005 (UTC)

[edit] All three classes are equal

The Caption for the pic at the top of the page says:"Diagram of complexity classes provided that P ≠ NP. If P = NP, then all three classes are equal." which is incorrect. If P=NP there will still be problems which are not NP-complete.--SurrealWarrior 02:19, 19 Jun 2005 (UTC)

No, that's not true. NP-completeness is defined with respect to polynomial-time many-one reductions. Every problem in P is trivially complete under this sort of reduction (simply solve the source problem and produce a yes/no instance of the target problem). Consequently, if P=NP, every problem in P=NP is NP-complete. Deco 08:26, 19 Jun 2005 (UTC)

This discussion is over a year inactive, but I want to point out that the caption IS wrong because a decision problem where the answer is always "no" or always "yes" cannot possibly be NP-hard, yet is obviously in P. Eric119 06:01, 23 August 2006 (UTC)

You're right. These two problems (and only these two) would fail to be NP-complete. So NP-complete is equal to P=NP minus two problems. I'll revise the caption. Deco 16:37, 23 August 2006 (UTC)

Is there a source for your conclusion, Eric and Deco? It doesn't sound right. Always accepting and always rejecting aren't in a special class that acts differently from all other problems. rspeer / ɹəədsɹ 23:25, 23 August 2006 (UTC)

Hmmm. At first I thought these two problems were special, since they don't have both yes and no instances for many-one reductions to target (so it would seem that they could only be reduced to themselves). But Papadimitriou asserts: "All languages in L are L-complete." (Computational Complexity, section 16.1, pg. 398). If this is true it seems like the analogous property must hold for P and polynomial-time reductions. These two problems are a special case in Rice's theorem - I'm really unsure about this. Deco 03:43, 24 August 2006 (UTC)

Did some more research. In chapter 14 Papadimitriou asserts "For all we know P could be equal to NP [...] Everything in NP would be both polynomial-time computable and NP-complete." Now that I think more about this, I think this has to do with vacuousness in the definition of a many-one reduction. If there is no yes/no instance to target, there is no need for the reduction to translate such instances. I will add back the statement and add an appropriate citation. Deco 03:48, 24 August 2006 (UTC)

Again, it is obviously impossible to reduce a non-empty language to the empty language. Proof: If a language L is non-empty there exists x in L, and in order for a function f to be a reduction from L to the empty language, we must have f(x) in the empty language, which by definition is impossible. QED. So Papadimitriou's statement is not quite true, as there exist non-empty languages in P. Eric119 05:17, 24 August 2006 (UTC)

Your math sounds right, and this document supports you explicitly. The only possible explanation I can find is either that Papadimitriou glossed over these special cases, or he's using a special definition of reduction/completeness (yet his original explanation of reductions is informal and does not reveal such a special case). If he really did miss these cases, then the diagram on page 330, showing P=NP=NP-complete as an explicit scenario, is an even more explicit error. Deco 08:46, 24 August 2006 (UTC)

I think it depends on the definition of reduction. Specifically, if you use Turing reduction, a non-empty language can be reduced to an empty one by not using the oracle. But it's a long time ago that I was taught theoretical CS. -- Jitse Niesen (talk) 09:44, 24 August 2006 (UTC)

[edit] About the algorithm that accepts the NP-complete language SUBSET-SUM.

In the section "Polynomial-time algorithms", it writes:

"No one knows whether polynomial-time algorithms exist for NP-complete languages. But if such algorithms do exist, we already know some of them! For example, the following algorithm correctly accepts an NP-complete language, but no one knows how long it takes in general. This is a polynomial-time algorithm if and only if P = NP."

Then it gives a algorithm that accepts the SUBSET-SUM and claims that the algorithm is a polynomial-time algorithm if and only if P=NP.

But I think this conclusion is not very clear since the number of the program P which produces the suitable subset of S may depend on the size of S.

Furthermore, if we change the IF statement in the algorithm with

          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" if that was proved) and HALT

there is another problem: the length of the proof and the number of the program which produces the proof may also depend on the size of S.

ok, I have understood. The algorithm is correct.

If there is a polynomial time program to solve the decision problme SUBSET-SUM, let P_0 be the number of such program. Note that P_0 is independent of the size of input for the SUBSET-SUM problem.

We can use the program numbered P_0 to construct a polynomial time program which produce a subset of S which adds up to 0. Let P_1 be the number of this new program. Note that P_1 is also independent of the size of input.

Assume the input S does has a subset which adds up to 0. Let N_1 be the number of steps need for program numbered P_1 to produce the correct subset of S. Since program numbered P_1 is a polynomial-time program, N_1 is a polynomial of the size of S. Therefore the algorithm will halt when N = max(N_1, P_1), P = P_1, and clearly it runs in polynomial time.

The second algorithm is similar.

---

For the above algorithm, we really do two things: 1) Search for P_0, and 2) Use P_0 on an input string. We say the overall algorithm runs in polynomial time with respect to the length of the input because task 1 is a fixed cost, and we assume P_0 is polynomial. That said, it is infeasible to search for P_0, so the algorithm is useless to us.

It is interesting to note that for short inputs, the algorithm will likely find a machine that just outputs the answer rather than solving the problem. But because such machines are themselves polynomial on the length of the solution, for large problems, we will eventually find the correct algorithm before we encounter any of these degenerate programs.

[edit] Better example for a problem in NP

I think the example definitely shouldn't be PRIMES. It is quite confusing there. How hard would it be refer to the SAT problem there? --Exa 00:05, 23 January 2006 (UTC)

Quite difficult. Really, just try to explain SAT in 50 words or less to someone who's never heard of it - perhaps never even heard of logical propositions. I like the composite problem because it's very simple, very obviously in NP, and familiar even to people with only a middle-school math education (although an NP-complete problem would be nicer). Deco 01:27, 23 January 2006 (UTC)

How about TSP or Hamiltonian cycle? The idea of finding the shortest circuit which travels through a bunch of towns before arriving back at the starting point shouldn't be too hard Keithdunwoody 03:27, 18 February 2006 (UTC)

subset sum problem. --Robert Merkel 05:02, 29 March 2006 (UTC)

[edit] Stupid Joke about P = NP

Commonly stated, this is P = NP, which is an assignment statement in most programming languages. The result of the condition is true if NP is true. So:

 if (P = NP)
   print TRUE
 else
   print FALSe

prints true if NP is true.

[edit] "Polynomial-time algorithms"

The article describes an algorithm that takes an enumeration of all programs, then runs programs 1..N for N steps each, for N = 1 to infinity. Then it says:

This is a polynomial-time algorithm if and only if P = NP... If P = NP, then this is a polynomial-time algorithm accepting an NP-Complete language. "Accepting" means it gives "YES" answers in polynomial time, but is allowed to run forever when the answer is "NO".

Perhaps I am mistaken, but I think this is complete nonsense. The "algorithm" is not an algorithm at all, since it is not guaranteed to halt, and in fact won't halt if there is no solution for the problem it is trying to solve.

I suggest that the entire section be deleted, and unless there is a serious objection in a few days, that is what I am going to do. -- Dominus 20:22, 5 April 2006 (UTC)

An algorithm does not need to halt in this context. -- Jitse Niesen (talk) 04:49, 6 April 2006 (UTC)

[edit] trivia

on the margins of 'concrete mathematics' by knuth, there is a 'proof' that P=NP; it says simply N=1 => P=NP! :)--Aryah 18:02, 16 April 2006 (UTC)

[edit] The second algorithm IS NOT CORRECT!!!!

         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" if that was proved) and HALT

There is no Turing Mashine, that can understand a "complete math proof".

Proof: If that there is the TM, we can solve Halting problem. We've got a TM, and we want to know if it stops. Let's search for complete math proofs and check them. Any TM either stops or not, so eventually we'll find a proof that TM stops or proof that TM doesn't stop. Hence we can solve the halting problem. But it is impossible.

I propose to delete this algorithm. —The preceding unsigned comment was added by 194.85.83.201 (talk • contribs) 17:07, 8 May 2006 (UTC)

Not only do Turing Machines that can check a "complete math proof" exist, such algorithms have even been implemented. One of the programs that check proofs is Coq. Your argument assumes that there either exists a proof showing that the TM halts, or there exists a proof showing that it does not halt. I think the conclusion of your argument is that there are Turing Machines for which such a proof does not exist. -- Jitse Niesen (talk) 01:15, 9 May 2006 (UTC)

"Every 'function which would naturally be regarded as computable' can be computed by a Turing machine."(Church–Turing thesis). So if some program can check proofs, then there is a TM can doing it. It's very difficult to understand / can exist TM, for which there is no such proofs, but if they do exist, why every word for every language has to have a proof, that it is not in the language(or proof, that it is in the language)? I mean why the second algoritm hopes that it will find a proof?

I've deleted the algorithm.194.85.82.254 05:04, 20 May 2006 (UTC)

Why? The Clay Math Institute Official Problem Description (pdf), listed in the External links section, says that "formal proofs can easily be recognized in polynomial time". So, I reinstated the algorithm.

If your reason for removal is supposed to be explained in the fragment "It's very difficult to understand … find a proof?" above, then could you please reformulate that? I have no idea what it means, and I couldn't even tell whether it was supporting your argument or not. By the way, it's useful if you could make an account or at least sign with the same name every time, since your IP address changes, which leaves me wondering whether you're the same person or not. -- Jitse Niesen (talk) 05:59, 20 May 2006 (UTC)

[edit] Another question about the second algorithm

The algorithm that decides subset-sum seems to rely on an unstated assumption: if P=NP, then there exists an algorithm that decides subset-sum and outputs a complete mathematical proof in polynomial time. This wasn't at all obvious to me, and it was fairly non-trivial to prove. Is it worth including a proof, or at least a pointer to one? -- Nate Biggs 21:07, 6 June 2006 (UTC)

Pointer to one would be good. I wouldn't put a proof here personally, but that's just because I don't really like that section. Deco 23:11, 6 June 2006 (UTC)

Any idea where one might find a pointer to one? Personally, my preference would be to delete the first algorithm entirely (who cares if there's a program that accepts subset-sum? That has nothing to do with P=NP) and include a short sketch of the proof that the second algorithm is correct. -- Nate Biggs 20:23, 8 June 2006 (UTC)

[edit] Article needs easily-understandable practical example

This article should have a more easily-understandable pratical example for the less tech/math-savvy ones, such as this one.

I can't write one myself, if that's what you're thinking. --Procrastinator 17:11, 31 July 2006 (UTC)

[edit] Maze theory

Isn't this the same as saying "given a randomly generated maze, is there a general algorithm for finding a route between entrance exit which does not involve taking every path" ?

Suppose I generate a random maze which has exactly one route between entrance and exit. If I then draw a line on it, you can easily verify if the line connects the entrance with the exit.

Now imagine I come up with an algorithm that finds that path without taking every possible route. So far so good. But what if I now move the exit so it lies on one of the unexplored routes. Now I must continue running the algorithm until the new route is found. At this point I again move the exit to another unexplored route. I continue doing this until all of the maze has been covered.

Thus there can be no general algorithm for finding the path between entrance and exit. QED.

Is this correct, or have I made a mistake somewhere ?

-- salsaman@xs4all.nl 29 Aug 2006.

What exactly are you trying to prove? It's not clear to me. The statement, "Thus there can be no general algorithm for finding the path between entrance and exit.", is false. You can always use breadth-first search to find the shortest path or discover that there is no path. Eric119 01:40, 30 August 2006 (UTC)

That's true. What I meant to say is "there can be no general algorithm that guarantees finding the single route solution without trying every route". But perhaps I am simply misunderstanding the problem. -- salsaman@xs4all.nl 1 Sep 2006.

There are several problems with this approach. One is that, because the maze itself is part of the input, even a search of the entire maze requires only linear time, which is polynomial (assuming a reasonable encoding). Another problem is that for any particular instance, the goal node is fixed; you have not established the existence of a single goal node that forces the search to visit every location. Yet another problem is that you have not established that this problem is NP-complete (and it's not) - there are many problems for which finding and verifying solutions can both be done in polynomial time, but none of them are known to be NP-complete. Deco 03:05, 2 September 2006 (UTC)

Thankyou. Your answers are helping me to understand the problem better. Reading it all through again it makes more sense. However there seems to be a contradiction on the page, it says:

'If P = NP, then this is a polynomial-time algorithm accepting an NP-Complete language. "Accepting" means it gives "YES" answers in polynomial time, but is allowed to run forever when the answer is "NO".'

I don't understand this. If there is an algorithm which finds a solution in polynomial-time, then surely it should just terminate after the maximum number of steps, and say that the answer is "NO". Why would it need to run forever if the answer is "NO" ? If it can't say "NO" in a finite time, then that means there could still be a solution left to find.

-- salsaman@xs4all.nl 02 Sep 2006.

More importantly, I guess what I meant by the maze analogy, and moving the exits is, what about Godel's theorem ? What I mean by this is, consider the subset-sum problem. I conjecture that for any proposed solving algorithm you give me, I can construct an input set which you can't solve in polynomial time. For example, suppose the algorithm starts with the lowest numbers first. I can simply construct a set with a solution 1,000,000 and -1,000,000, and fill all the rest with small numbers. If the algorithm starts with biggest numbers first, I can construct a set with 1 and -1 and fill the rest with larger numbers. If the algorithm starts by considering pairs, then triplets, I construct a set where all the numbers must be summed to reach 0.

All I need do is look at the algorithm, and figure out a way to "break" that algorithm, i.e. construct a set where the solution will be the last possible combination tested.

-- salsaman@xs4all.nl 03 Sep 2006.

In short, yes, it's easy to come up with counterexamples that indicate why a particular heuristic strategy is not polynomial-time in the general case. The difficulty is finding such counterexamples for all possible solutions, of which there are an infinite number, most of them very complex. Don't forget that the algorithm can alter its behavior depending on the specific input, which includes the location of the goal. I'm also unclear on the "allowed to run forever on NO" thing - complexity (as opposed to computability) generally only considers algorithms that always terminate. Deco 10:21, 3 September 2006 (UTC)

But isn't that precisely what Godel's theorem says: for any consistent formal theory (algorithm) that proves basic arithmetical truths (solves the subset-sum problem), it is possible to construct an arithmetical statement (input set) that is true (has a solution) but not provable in the theory (solvable in polynomial time). Secondly, wouldn't finding an "algorithm breaking" input, itself be an NP-complete problem ? Thus if P==NP, I could find such an input in polynomial time, and then feed it into the first algorithm ! Finally, regarding the quote, I cut and pasted it from the article page. It's also mentioned above, "polynomial-time algorithms". Look for yourself ! My point is, the program should always be able to halt ! It just needs to compute the maximum time it would take to find a solution - if it can find it in polynomial time, then this should be just a function of the input length. Then if no solution is found in this time, it outputs "NO" -- salsaman@xs4all.nl 03 Sep 2006.

Answering my own first question, I suppose that if Godel's theorem were true for NP-complete solvers, then I would just construct a third algorithm, which finds a "second algorithm breaker". Then that second algorithm breaker would be my chosen solution for the subset-sum problem. But this leads to a contradiction - which implies that either an NP-complete solver would not be a consistent formal theory, or that P!=NP. I don't know what to make of this. I am probably stating something obvious, but I've not seen things expressed in exactly this way elsewhere.-- salsaman@xs4all.nl 3 Sep 2006.

Answering my own question again. I suppose a set with an infinite number of elements could be solved in polynomial time, but that time could also be infinite. So this would be the application of Godel's theorem... And given such an infinite set, it could take an infinite amount of time to produce a "NO" answer, so that also addresses my other point. -- salsaman@xs4all.nl Sep 03 2006

[edit] P=NP?

I noticed THIS on arxiv.org: [1] and [2] 70.49.174.170 01:23, 5 September 2006 (UTC)

Well, all seem more complicate. I don't know if author of this papers is right or wrong. Have a look, people, if you feel competent.70.49.174.170 01:46, 5 September 2006 (UTC)

For the purposes of wikipedia it doesn't matter yet: it's dated sept 2 2006: any serious claim of such a proof would go through scrutiny from the scientific community and then either a flaw would be found or it would become gennerally accecpted. Unless if something gets into a peer reviewed scientific journal I don't think it would be worth mentioning. GromXXVII 02:04, 5 September 2006 (UTC)

There are lots of preprints floating around that claim to prove or disprove P=NP. Unless and until this one gets more scrutiny we'll have to reserve judgement. This one doesn't contain any signs of obvious crackpottery in the first two pages, which is an improvement on at most such preprints. --Robert Merkel 02:19, 5 September 2006 (UTC)

OK, the paper is mentioned here. Diaby has been working on this for a while, and it's been discussed extensively on the comp.theory newsgroup. They don't accept it, and he hasn't been able to interest any of the academic theory community in his result. --Robert Merkel 02:33, 5 September 2006 (UTC)

I have read this article and it seems odd for me. Author reduces TSP to LIP (Linear Integer Programming is known to be NP-hard, so TSP can be reduced to LIP - nothing new), then he construct non-integer version claiming that solution to this non-integer version allow to answer TSP problem. As we know non-integer linear programming is most often polynomially bounded (in terms of time used), but no one (before this paper) proved that integer programming may be reduced to non-integer version. Well... incredible ;-).

There are several methods for proving theorems – proof via symbol over-usage, proof by hands weaving, proof by authority (Simon says...), proof by discrete change of assumptions, proof by negation of assumptions, proof by assumption that thesis is true, proof by mumbling and so on :-). This proof is hard to understand because of symbol over-usage, but in my opinion possible to be found false.

Meanwhile - I have developed my own very formal proof that P < NP - it is being under review by Discrete Applied Mathematics and hopefully will be available next year :-). See My HomePage. --Hcsradek 9:55, 7 September 2006 (GMT+2)

You forgot one: proof by removing your article from a website :-) -- anonymous.

I have an excellent proof of P ≠ NP, but it is too large to fit in the margin of this talk page. Deco 10:50, 10 September 2006 (UTC)

Proof by removeing is cool :)... but it was not main idea - I have prepared short summary, and it is avaliable here. --Hcsradek 11:39, 18 September 2006 (GMT+2)

It took longer then I expected but now I can formally prove that article [3] is incorrect. Counter example for this model is avaliable in mine article here --Hcsradek 14:54, 20 October 2006 (GMT+2)

Returning to my "maze theory" above - somebody was asking for an example for non-mathematicians. Somebody suggested a breadth-first algorithm for finding the exit. A breadth-first search is an example of an NP-complete algorithm. My point, before I distracted myself (!), was this: Example for non-mathematicians: you are standing at the entrance to a maze. You know for a fact there is exactly one other exit from the maze. The challenge is this: can you walk to that other exit without trying each possible path through the maze, and without just stumbling on it ? Most people would say no, but can you prove it one way or the other ?

-- salsaman@xs4all.nl 10 Sep 2006.

Salsaman, we've already added an easy to understand example of an NP-complete problem at the top of the article: subset-sum. It's about as simple an example as you can get. Adding woofly analogies to ill-defined problems is not likely to improve comprehension any further. --Robert Merkel 02:25, 11 September 2006 (UTC)

[edit] History

Please could everyone look at the reverts in this article, I have been trying to revert some blatant opinion expressing but I'm having trouble with user:82.250.60.102, please check and make your opinion on the matter as I have little knowledge of the subject Ryanpostlethwaite 17:47, 23 November 2006 (UTC)

If you have little knowledge of the subject, please move on... 82.250.60.102

Please check over the history for a few edits ago. We have come to an agreement now and in my opinion his new propsal of the title (see edits) is no longer biased. But I am still erring on caution so please check and ammend appropriatly Ryanpostlethwaite 18:00, 23 November 2006 (UTC)

I'm sorry but this line IS an opinion which I've just removed as other people have different views on P=NP; 'However, holding such belief for such reasons is tantamount to believing that Higgs Boson does not exist' Ryanpostlethwaite 22:06, 23 November 2006 (UTC)

I'd agree with you there Ryan. I'm not an expert in the subject but 82.250.60.102's edits read like soapboxing to me. However, Wikipedia has a three revert rule, so if it's a big issue you need to look into Wikipedia:Resolving disputes. — jammycakes 22:23, 23 November 2006 (UTC)

If you are not an expert then do not even think about anything as being soapboxing or not being soapboxing. Ryan could not be aware of three revert rule, he just arrived in town. The only big issue here is people like Ryan or Jammycakes expressing their opinion through reverts, supposedly in order to prevent violation of non-opinion policy. Ryan is the violator. user:82.250.60.102

I don't think we will need to go through Wikipedia:Resolving disputes. I'm confident that anybody who knows a bit about P=NP will agree that "Some computer scientists may err in professing that P≠NP" is not a neutral formulation and that 82.250.60.102's edits should be reverted. -- Jitse Niesen (talk) 02:56, 24 November 2006 (UTC)

This is your opinion about which you are confident. By the way, I know quite a bit about P=NP. 82.250.60.102

I think now that this is highly out of order, you have 3 neutral people saying that the items you added are biassed yet you still persist to revert the edits back to yours. By all means lets discuss this on the talk page BUT User:82.250.60.102 needs to reflect on what everyone else is saying Ryanpostlethwaite 11:16, 24 November 2006 (UTC)

Neutrality is by no means a way of deciding what is the right thing for this Wikipedian entry. If you were talking about knowledgeable or competent people, then I guess one could listen to your "all means". 82.248.114.187

(copied from User talk:82.250.60.102, addressed to him/her): You have given no valid reason at all for why you want to change the paragraph in the article. You said in this edit summary that the original paragraph was expressing an opinion. However, the original paragraph said "Most computer scientists believe that P≠NP", which you want to replace with "Some computer scientists may err in professing that P≠NP". Surely, your version is more opinionated in that it implies that in fact P=NP. You also said in this edit summary "please discuss in the talk page". Well, it is rather hard to discuss it without knowing why you want to change it. By all means, tell your arguments and I'm interested to discuss it. However, editing the article without giving any arguments when requested will not do. -- Jitse Niesen (talk) 11:29, 24 November 2006 (UTC)

The original paragraph did say that "Most computer scientists believe that P≠NP". This is as much an opinion as saying "Some computer scientists may err in professing that P≠NP". What source do you have to backup this majority statement? How do you know "most" computer scientists believe that? Would any of us see this as a "belief"? ... Well, that's maybe the only point where this statement comes close to truth... P!=NP became a belief for some colleagues. You ask for "arguments". Did anyone bring up evidence that "most computer scientists" think so? If you knew just a bit about the subject, you would think twice before deleting the analogy with the existence of Higgs boson. 82.248.114.187

The only reasonable way by which you could change your paragraph (if you still believe that Wikipedia should defend this "original" opinion) would be to say: "Computer scientists of the Bill Gasarch type believe that P≠NP". He (and SIGACT) is your only source. Wake up. 82.248.114.187

The point that I am trying to make is that although you may think it is absurbed that some people believe that P≠NP, there are some people who think that this is correct. The analogy with the existence of Higgs boson suggests that the people that believe P≠NP are stupid and completely incorrect, this is an opionion that you are expressing as I am sure the people that believe P≠NP would have a far different opinion. The paragraph in question is showing why people believe that P≠NP and it is not trying to show that this is correct. Therefore the changes that you made are unhelpful and need reverting to keep the articles neutrality Ryanpostlethwaite 21:41, 25 November 2006 (UTC)

May I make one suggestion, that we change the title of the paragraph from 'most computer scientists believe that P≠NP' to 'some computer scientists believe that P≠NP'. That may even improve the overall neutrality of the paragraph, but all other edits on this paragrph were opinionated and therefore should not be kept Ryanpostlethwaite 21:59, 25 November 2006 (UTC)

Earlier in the article, it says (I long ago added this):

In a poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.

So, uh, yes, I interpret that as "most computer scientists believe P ≠ NP", or more accurately, most believe there is strong evidence that P ≠ NP. In any case I think I provided ample counterpoints in that section already in the quotations, and the claim that Higgs Boson is even related to the pure mathematical result of whether P ≠ NP seems silly to me and I wouldn't believe it without a verifiable source. Even then, the wording "some may err" is strongly implying that those computer scientists believing P ≠ NP are wrong. Please leave it like it is and if you can find a source for this Higgs Boson stuff, talk about it somewhere else in the article. Deco 07:05, 26 November 2006 (UTC)

As already said... This poll just reflects what Bill Gasarch made it to reflect. Ryan's change for the title seems sound. As for relating Higgs Boson to this pure computer science result, Deco is clearly unaware of what's silly and what's not. "Some may err" is as strong as saying in the title "Why computer scientists think..." (which implies an absolute opinion of all computer scientists). I will propose a new version beyond Deco's dictatorship and my own stubbornness. 82.253.212.117

You haven't offered any support for this claim that Gasarch in any way forced the result of the poll. Really I'm surprised that as many as 9 out of 100 would think that P=NP, which I think is pretty obviously extremely unlikely. I strikes me as quite plausible that most computer scientists think P!=NP, the much more intuitively reasonable outcome, especially given the coherent picture of the polynomial-time hierarchy that has emerged.

However if you have some countervailing evidence to Gasarch's poll, then please present it. Otherwise I personally will oppose any change in the direction you suggest (including Ryan's proposed change, because we have a prima facie case that "most" computer scientists in fact believe P!=NP, and I see no reason to water it down). --Trovatore

Go for "many", though the many may be wrong (but that's obviously not the problem of Wikipedia). 82.253.212.117

I think now that we have finally gained consesus! If all are agreed we will leave the heading 'most computer scientists believe that P≠NP' and the subsequent paragraph intact and revert (as already done so) all changes made to it. Many thanks for everyones contributions Ryanpostlethwaite 23:37, 26 November 2006 (UTC)

[edit] Questions

Hi all, not an expert but find the subject very interesting. The debate over this question has a lot of interesting elements at its core. Basically, I think this is one of the most philosophically unique debates in science. First, its resolution has important consequences for several fields. I also think the nature of the dispute is interesting, in that (at least, as the dispute is represented in this article,) the people who say P!=NP are making an empirical argument based on current failure despite lots of effort, while the proponents of P=NP are holding out for a theoretical proof. Thanks for all of your energetic and thoughtful development of the article.

Due to the nature of the dispute, I find myself jumping a bit into the future, and I have a couple of questions for people who really think about this stuff. Any discussion would be great, and if you could post your reply on my talk page so that I would see it I would be very appreciative. Again, these are just some questions, I profess very little previous exposure to the subject.

Questions: Given the differing nature that seems to be emerging among the two "camps" on this question, and given the way that the question is formulated, how would a theoretical proof that P<NP even look or work? It seems that the "proof" that P<NP would simply be a sufficiently long list of examples of things like subset-sum, at least if current approaches to the question continue. I know this question seems silly, in that we don't know what the proof will look like until we find it, but I'm asking more generally how a question like this could even be resolved. I don't understand fully the interactions between the question and challenging examples, such as subset-sum.

IF P=NP, does that mean necessarily that every question like subset-sum must have an expedient answer and we just haven't found it yet? Therefore, does it mean that in EVERY persisting example where seemingly P<NP, all parties have overlooked a stroke-of-brilliance way to answer the example question that is as quick as it is to verify it? This seems exceedingly unlikely, doesn't it? Another way to ask this question is to say: does P=NP have to hold for everything to be considered true? Thus, if P=NP, does that mean that it is IMPOSSIBLE to dream up a question which is long to answer but quick to verify?

It seems to me that the philosophy of P=NP, the underlying claim, is that there is a fundamental identity of both answering a question and verifying the answer, that they must by definition have such a close brotherhood that, when the issue is fully explored and properly understood, their computational requirements converge. Something like subset-sum is currently easier to verify than to prove. Let's say, for sake of argument, that we figured out THE fastest way to verify a subset-sum answer, and it's x amount of time. Does P=NP, if true, imply that we have also found the amount of time that the perfect method would require to answer a subset-sum question, even if we have no idea what that method is?

Thanks for your help! Gcolive 20:58, 13 January 2007 (UTC)

Great questions, Gcolive. I'll try to directly answer some of your specific points. This doesn't have much to do with improving the article, but what the hell.

"the people who say P!=NP are making an empirical argument based on current failure despite lots of effort [...] IF P=NP, does that mean necessarily that every question like subset-sum must have an expedient answer and we just haven't found it yet? Therefore, does it mean that in EVERY persisting example where seemingly P<NP, all parties have overlooked a stroke-of-brilliance way to answer the example question that is as quick as it is to verify it? This seems exceedingly unlikely, doesn't it?"

You have described quite well the reason why many people believe P ≠ NP. On the other hand, some of the deepest results in complexity theory were the proofs of NL=coNL (Immerman-Szelepcsényi Theorem) and L=SL. At one time a logspace hierarchy analogous to the polynomial hierarchy was defined, but turned out to be trivial. And it wasn't that people hadn't tried to find efficient algorithms for NL-complete problems, although they certainly haven't received the heaps of attention NP-complete problems get.

how would a theoretical proof that P<NP even look or work?

That's just it - we have no idea. We know that P ≠ EXP by the Time hierarchy theorem, a basic diagonalization argument, but oracle results show that this won't work for P ≠ NP. Likewise, we know that AC⁰ ≠ NC, because it does not contain the parity function, which was probably the most important separation result of recent times. But the theory of natural proofs tells us that similar ideas won't prove P ≠ NP. In short, pretty much everything that ever worked, won't work - we need something new.

Let's say, for sake of argument, that we figured out THE fastest way to verify a subset-sum answer, and it's x amount of time. Does P=NP, if true, imply that we have also found the amount of time that the perfect method would require to answer a subset-sum question, even if we have no idea what that method is?

Sort of. It tells us that solving it is at worst polynomially slower than verifying it. For example, verifying it might require O(n²) time asymptotically, whereas solving it requires O(n⁵) time. A great example of this is primality certificates, which are short proofs of a number's primality that (today) can be verified more quickly than their primality can be established, even though this problem is in P (ref AKS primality test). Nevertheless, yes, P=NP would prove (perhaps nonconstructively) the existence of polynomial time solutions to any problem for which we have a polytime verifier.

Thus, if P=NP, does that mean that it is IMPOSSIBLE to dream up a question which is long to answer but quick to verify?

Roughly speaking, yes. It can still be polynomially slower to solve than to verify, and it may still be the case that a separation exists at higher levels of complexity, somewhere above NEXPTIME.

the proponents of P=NP are holding out for a theoretical proof

I'm not sure I'd go quite that far - there aren't many "proponents" of P=NP at all, and most people who believe that seem to believe it in analogy to other results like the ones I mentioned above. The people who "aren't sure" though are waiting for a proof and more importantly for the tools that would be needed to construct such a proof.

Hope this helps. Deco 08:23, 14 January 2007 (UTC)

[edit] Confusion

Hello all, I'm trying to understand the "Polynomial-time algorithms" section of the article. I'm not convinced that if P=NP, that in fact an algorithm for an NP problem must be polytime. I was under the impression that a proof that P=NP would imply that there existed an equivalent polytime algorithm, not that a particular algorithm must be polytime. Can someone explain this to me? Arkleseizure 21:48, 27 January 2007 (UTC)

Your question is a bit vague. Which part of the argument do you not follow? Do you not believe the given algorithm is correct, or do you not believe it runs in polynomial time (given P=NP)? --Mellum 22:02, 27 January 2007 (UTC)

I think Arkleseizure is making the point that the article claims that "if P=NP then any algorithm for an NP problem runs in polynomial time", which is not true. However, I don't see where the article makes this claim. -- Jitse Niesen (talk) 07:55, 28 January 2007 (UTC)

[edit] Good job

Hello, I just read the entire article and I want to say good job to the people who wrote it. This is a very complex subject but you people have found a way to explain it in a simple, clear, easy to understand way. Good Job. 70.49.201.164 03:12, 4 February 2007 (UTC)

[edit] Formal Definition

Why is (Note that the abbreviation NP stands for "Non-deterministic Polynomial" and not for "Non-Polynomial".) at the end of the Formal Definition section? It should be readily available in the introduction to this entry.

[edit] Independent of axioms

The article vividly explains the evidence, theoretical arguments, potential consequences, and history surrounding the statements P≠NP and P=NP. But Gasarch's poll found that some researches believe that the statements are independent of the accepted axioms. I feel that this article should give that viewpoint equal exposition as it gives the other two. Otherwise, terrific article. Thanks! --131.193.178.113 20:53, 13 February 2007 (UTC)

A good point. We really ought to discuss this viewpoint in more detail, but frankly it involves a deeper background in logic, and I don't think I could explain it myself. I might be able to find some references or hopefully some contributors who know better than I. Deco 21:42, 13 February 2007 (UTC)

Independent of which accepted set of axioms? Peano arithmetic? ZFC? Something in between, or something stronger? It makes a difference -- "independent" is not a truth value, contrary to some people's vague notion of the idea. Those who responded in that way to the poll may have had viewpoints sufficiently disparate among themselves that no single coherent exposition will really be possible, and in any case we don't have a reference for just what it was that those who responded thus were thinking. (Or I assume we have no such reference -- if anyone does have it, of course please share.) --Trovatore 22:07, 13 February 2007 (UTC)

Usually ZFC. We have a reference for some of them at least, that are quoted in the poll paper. Deco 02:56, 14 February 2007 (UTC)

Hm, I took a look at the poll paper, and the author guesses they were talking about ZFC, but we have nothing from the respondents. Except that three other respondents said it was not independent of PRA! So I don't think we have much to go on here. Independence from ZFC, as opposed to other stronger or weaker theories, is nothing special, and no particular reason to single it out. --Trovatore 05:15, 14 February 2007 (UTC)

[edit] New discussion

All,

Ok, I've asked nicely for my edits here and in Wikipedia:Love, Wikipedia:Life to be left in-situ, but there seems to be a persistent desire to remove them. Since the addition logically invalidates the rest of the article here and articles elsewhere I guess the revertees are protecting sunk investment. Ho Hum.

I will not put the additions back on Wikipedia again.

Your choice.

-matt dspart 16h10, 26 February 2007 (GMT).

So what exactly do love & life have to do with P and NP? Why did you vandalize this article because of reverts on those articles? Why are you complaining about those reverts here instead of on those 2 talk pages? It's pretty clear your "additions" to those 2 articles are nonsense. Blokhead 22:36, 26 February 2007 (UTC)

Blokhead (apt, perhaps? Seriously, are you cube-shaped? Have N of M components in structured groups? Have an ultimate "Queen" for your drones? Need Data? I might have some...),

Re. Love, etc. Triangulated place-holder in, well lets call it a tuple-space for now.

Re. "nonsense": E=mc^2, and you *fully* understand that, right? Understand it a little? Heard about it? Got a t-shirt with it on with an old guy sticking his tongue out, maybe.

So, "pretty clear" then, eh? I think not. However, instead of dismissing it out of hand, I'm will to listen to arguments which show any fault with the logic here, or that this is incorrect.

To put my money where my mouth is (and, yes there is some), I bet you *or anyone, anywhere* publicly, every single penny that I have - or a choccy bar, Kip Thorn - that P=NP . In *one* line. For it is Extraordinary Proof/HowdyDoody Time, LOL.

Also, there's a much better solution to that Fermat's Last (4 lines), but I can't be arsed.

Think consequences. Think Hiroshima.

Anyhow, better things to do than talk to Blokhead[s]. Mornington Crescent to you, again, BTW.

-matt dspart 23h00, 26 February 2007 (GMT).

I'm going to agree with dspart, but only because I'm drunk. --131.193.179.146 04:10, 1 March 2007 (UTC)

Retrieved from "http://en.wikipedia.org../../../c/o/m/Talk%7EComplexity_classes_P_and_NP_1133.html"

Categories: Unassessed-Class Computer science articles | Unassessed-importance Computer science articles | Bplus-Class mathematics articles | B-Class mathematics articles | High-importance mathematics articles