Talk:Complexity classes P and NP
|
|
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 (http://www.ics.uci.edu/~eppstein/cgt/hard.html), 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 (http://www.claymath.org//Popular_Lectures/Minesweeper/) 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.
| Contents |
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(nlog 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 (http://www.win.tue.nl/~gwoegi/P-versus-NP.htm), 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)
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)
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.