can someone explain to me why it's so important that N!=NP?

>>7779201
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.

>>7779201
it's obvious that you open the thread with something interesting that you may or may not already understand just so you can hide you homework question in the end

fuck off

>>7779215
i read that and it seems silly because the algorithms required to break cryptography wouldn't magically appear out of thin air just because we've proven them to exist. or am i wrong about that?
>>7779217
k

>>7779227
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.

>>7779235

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.

File: 010.jpg (72KB, 1051x591px) Image search: [Google]

72KB, 1051x591px

>>7779215
integer factorization is NOT considered to be an NP Problem

>>7779235
>>7779215
stop the meme. absolutely no, it's not a threat. there's no reason to think a polynomial algorithm will have feasible constants and less to think that we'll be able to magically come up with it just by knowing it exists

File: 1.gif (232KB, 450x675px) Image search: [Google]

232KB, 450x675px

>>7779201
youtube it, faggot: there're plenty of good videos on the subject

>>7779227
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

>>7779386
If you consider the integer factorization problem as a decision problem (check the wiki page), then its in NP and co-NP.

>>7779201
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.

>>7779201
If P=NP we are a couple reductions away from skynet pretty much. Lot of problems in AI, computer vision and NLP are in NP.

>>7779386

You're mixing up NP with NP-hard

Almost all problems are NP, even everything in P.

>>7777777

File: neuspiel.png (830KB, 567x558px) Image search: [Google]

830KB, 567x558px

>>7780212
sorry, you're wrong

wiki:

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.[3] 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?

>>7781095

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.