can someone explain to me why it's so important that N!=NP? i don't get it. what's so different if something can be expressed as a polynomial? i read the implications on wiki but those seem weird, like cryptography breaking down etc.
pic sort of related, is that even a polynomial?
If P = NP then that means problems that were before non-polynomial can now be solved in polynomial time. This has huge implications on cryptography in particular because modern day cryptography is based on prime factorisation which is currently an NP problem (a problem that cannot be solved in polynomial time). If it was proved that P = NP then these forms of cryptography would be "broken" and big problem would follow.
But it's the threat though isn't it?
Just the threat that someone has derived an algorithm that can crack any encryption without requiring insider knowledge. Surely that level of fear is enough to cause the entire system to fall apart.
a proof that P = NP can only have practical implications if it's a constructive proof.
even if we do have a constructive proof, we still need to be able able to carry out the reduction of some NP-complete problem to some problem in P in a reasonable amount of (polynomial-)time. for instance, if we're only able to give a reduction that takes O (n^G), where G is graham's number, then we're really no better off than when we just assumed that P != NP.
integer factorization is NOT considered to be an NP Problem
youtube it, faggot: there're plenty of good videos on the subject
It depends on how P = NP is proven - If its proven by showing that an NP-complete problem is in P, then we get an explicit algorithm to solve every problem in NP using polynomial time
If you consider the integer factorization problem as a decision problem (check the wiki page), then its in NP and co-NP.
N is the set of problems that can solved in a "small" amount of time by a conventional 1-processor computer.
NP is the set of problems where a potential solution can be verified correct in a "small" amount of time by a conventional 1-processor computer.
This matters because there are a lot of problems in NP that people like me want to find solutions for with computer algorithms, and it would be really nice to know if it can be done quickly.
No one has found a "quick" solution yet, and on that scientific basis, most people believe that P is different than NP.
sorry, you're wrong
It is not known exactly which complexity classes contain the decision version of the integer factorization problem. It is known to be in both NP and co-NP. This is because both YES and NO answers can be verified in polynomial time. An answer of YES can be certified by exhibiting a factorization N = d(N/d) with d ≤ M. An answer of NO can be certified by exhibiting the factorization of N into distinct primes, all larger than M. We can verify their primality using the AKS primality test, and that their product is N by multiplication. The fundamental theorem of arithmetic guarantees that there is only one possible string that will be accepted (providing the factors are required to be listed in order), which shows that the problem is in both UP and co-UP. It is known to be in BQP because of Shor's algorithm. It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete. It is therefore a candidate for the NP-intermediate complexity class. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find classical polynomial-time algorithms for it and failed, and therefore it is widely suspected to be outside P.
>It is not known exactly which complexity classes contain the decision version of the integer factorization problem. It is known to be in both NP and co-NP.
>It is known to be in both NP and co-NP.
did you even read what you posted?
I think what he's saying is that you're confusing NP-complete and NP. If you find an NP-complete problem is actually in P then you simply get algorithms for everything in NP-Complete, since there's reductions between them all in polynomial time. Of course this means you get stuff like integer programming, SAT, etc, which should make it trivial to get your algorithm solved in polytime.