Talk:P versus NP problem/Archive 1

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.

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)

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)

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)

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)

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)

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.

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)

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.

Why dont you just type "print the_sum_of_all_knowledge_possible" Youre clearly not using your magical computer to its full potential.

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

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)

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)

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)

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)