5 ms·
Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible
by cperciva 16y ago
Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time.
The issue of whether it's a feasible amount of work is exactly what I was addressing.
- dejb 16y agoSpeaking pedantically, P is in NP also. I suspect that NP is being used as shorthand for NP-complete, not just NP. As for actual deterministic factorization Wikipedia says that 'It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete' So even if this showed 'P = NP-complete' it may not imply imply factorization is in P. I'm at the limits of my rusty complexity knowledge here so if any knows better please correct me.
- bdr 16y agoActually, cperciva is right here. Factoring is in NP, therefore if P=NP then there is a polynomial-time algorithm for factoring. Many problems harder than NP are NP-complete, so saying factoring is in NP-complete would not imply the conclusion. Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.
- sonoffett 16y agoCperciva is right, but I think you're mistaken when you say "many problems harder than NP are NP complete", NP complete problems are both NP and NP hard. NP hard is a class of problems such that every problem in NP can be reduced to any problem in NP hard. Meaning if P=NP then every problem in NP(including the NP complete problems) can be solved in polynomial time; all it takes is one algorithm that solves an NP complete problem in polynomial time (note that this does not show that P=NP hard, a much stronger claim).
- bdr 16y agoYou're right. I've got the brain hiccups.
- dejb 16y agoThe point I was trying to make (badly) was that the actual claim doesn't imply P = NP, only that P = NP-complete. Given that factoring isn't known to be NP-complete (or co-NP-complete) this paper doesn't imply that factoring is in P.
- anorwell 16y agoIf a single NP-Complete problem is in P, then P=NP. This is what NP-Complete means. In particular, factoring would be in P. Conversely, factoring is not NP-complete, so if factoring were in P, we could not draw any conclusions about P=?NP.
- JadeNB 16y ago> Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete. Err, it seems to me you've got a very serious statement there. I think you mean “that are not known to be …”.
- bdr 16y agoYep. I should just stop posting today. :)
- JoeCamel 16y agoNo, there actually are problems in "NP-intermediate" class (if P!=NP) although they are artificial. :) And, of course you are right, for many other problems researchers suspect they might be in NPI. See http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc http://cstheory.stackexchange.com/questions/79/problems-betw...
- lmkg 16y agoIt's been proven that if P != NP, then there are problems in NP, which are neither in P nor NP-complete. We don't know what those problems are, because identifying such a problem would prove P != NP. There are candidates, such as factoring, for which there are neither polynomial algorithms nor proofs of NP-completeness, but definitively identifying them is at least as hard as proving P != NP, and possibly harder.
- dejb 16y agoTrue. 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.
- kd0amg 16y agoThe 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.
- RiderOfGiraffes 16y agoI 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.
- patio11 16y agoThe issue of whether it's a feasible amount of work is exactly what I was addressing. One of the reasons this would be a huge result is that even a very expensive polynomial-time solution for any NP-complete problem (say, one which is O(n^2000) and would take several billion years to run against a 256-bit key) is only going to get faster over time. Also, the experience of cryptography is that once cracks start appearing in an algorithm the mathematicians start trying to wedge their chisels in and hammer those cracks into fractures, into holes, and eventually into whatever you call something which no longer resembles a crack so much it resembles absence-of-wall. There are specific mechanisms by which this would happen, too. A near miss on P=NP would mean funding for professors looking into refining it, and professional interest generally, would suddenly explode. Nobody wants to fund or work on duds, but big contributions to this problem would make careers. Not incidentally, while the government funds quite a bit of academic research, this particular branch of mathematics is of special interest to one type of government customer which has ways of getting funding for projects expedited if they are in the national interest... and it is virtually inconceivable that they would not find very, very strong national interest in the vicinity of this result.
- deleted 16y ago[deleted]