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