[dejb]

True. However I don't think the article really implies that P = NP (although the title certainly does). From what I can see the article only addresses the class of NP-complete problems. Factoring is not known or believed to be NP-complete so it wouldn't directly prove that factoring was in P. Please correct me if I'm wrong.

Edit : For some reason I can't reply to posts so I'll do it here.

RiderOfGiraffes> It would will leave in question those problems in NP, but not NPC. Currently it is generally believed, but not known, that factoring is such a problem.

This is exactly my point. P = NPC doesn't imply anything about factorisation. Since factorisation is in NP we haven't shown that P = NP

kd0amg> NP-complete problems ... are, in essence, the hardest problems in class NP.

From what I understand they a 'thought to be' the toughest but this isn't proven. If this article turned out to be true then they are reduced to being as hard as P. So who is still standing as a contender for the hardest problem in NP? - factorization of course as it has never been demonstrated to be polynomially reducible to NPC.

[RiderOfGiraffes]

I believe you to be mistaken. Let me explain.

Proving that any single NPC problem is in P will be enough to prove that every NP problem is in P, and not just the NPC ones. Suppose A is is NP, B is in NPC, and further suppose that solving B is polynomial. Reduce A to B (a polynomial operation because B is in NPC), solve B (a polynomial operation by assumption), and convert the solution back to a solution of A (a polynomial operation because B is in NPC), and that gives a polynomial solution of A.

Proving that any single NPC problem is not in P is enough to prove that all NPC problems are not in P. It would will leave in question those problems in NP, but not NPC. Currently it is generally believed, but not known, that factoring is such a problem.

Added in edit, to reply to your edit:

    RoG> It would will leave in question those problems
    RoG> in NP, but not NPC. Currently it is generally 
    RoG> believed, but not known, that factoring is such
    RoG> a problem.

    dejb> This is exactly my point. P = NPC doesn't imply
    dejb> anything about factorisation. Since factorisation
    dejb> is in NP we haven't shown that P = NP

Read my entire comment again. In particular, the second paragraph. In particular:

    Proving that any single NPC problem is in P will be
    enough to prove that every NP problem is in P.

More specifically, proving 3-SAT is in P will prove that every NP problem, not just the NPC problems, but every NP problem, is in P. Including factoring.

Let me add a little more.

   1. Suppose 3-SAT is in P.
   2. Let A be any problem in NP.
   3. 3-SAT is in NPC.
   4. Therefore A can be converted to A', an instance of 3-SAT.
   5. By (1), A', as an instance of 3-SAT, can be solved in polynomial time
   6. Hence A has been solved in polynomial time.

Replace "A" with factoring, and thus we've shown that P=NPC implies that factorisation is in P.

[djtumolo]

Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.

[rincewind]

This in the definition of NPC. What you have to prove is that a language is in NPC.

This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

http://en.wikipedia.org/wiki/NP_complete

[RiderOfGiraffes]

By definition, a problem P is NPC if:

a. P is in NP, and

b. Every problem in NP can be converted to an instance of P.

Consider any two problems in NPC, P and Q. Then each is in NP, and each can be converted to the other. They are therefore equivalent.

QED.

[kd0amg]

The NP-complete problems are a subset of NP ("nondeterministic polynomial") problems, specifically those to which all NP problems are polynomial-time reducible. They are, in essence, the hardest problems in class NP. It's pretty trivial to show that integer factoring is in NP; what's not known is whether it's NP-complete. If any NP-complete problem is in P, then via polynomial-time reduction, all problems in NP are in P.

[amalcon]

factorization of course as it has never been demonstrated to be polynomially reducible to NPC.

Every NP problem is polynomial-time reducible to SAT. I do not recall the title of the paper off the top of my head, but it has been proven that the definition of an NP problem (a question that can be answered given some additional piece of information, a "certificate") is polynomial-time reducible to SAT.

The methodology was basically an algorithm taking as input a description of such a solution, and producing a boolean expression on the certificate and some other values needed to maintain integrity. The expression is satisfiable if and only if the answer is affirmative.

The reason that factorization is not known to be NP-complete is that the reverse is not known. That is, no NP-complete problem is known to be polynomial-time reducible to factorization.

[sid0]

From what I understand they a 'thought to be' the toughest but this isn't proven.

Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version).

So who is still standing as a contender for the hardest problem in NP?

If P = NP, then all problems in NP are as easy as each other, so this question is meaningless.

[eru]

To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median.

The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n).

Sorting and finding a median reduce to each other polynomially, of course.

Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problems whose runtime tends to O(log n) as the number of processors tends to infinity. Adding a list of numbers is not only linear but also highly parallelizeable. Proving a problem to be not parallelizeable like that, is also interesting.

There's also the question whether randomness helps. It does in practice, but we don't know whether access to random bits helps in theory.

[sid0]

By "as easy as each other" I meant reducible to each other with a polynomial factor, as is standard in complexity theory.

[eru]

Yes, that why I prefaced with "To be pedantic". I just felt like pointing out that there are meaningful differences between polynomial problems.