Does P = NP?

Does P = NP?

No.

No one knows. We just hope they don't or else all our cryptography would be in deep shit. Then again, if you actually found proof that P = NP, would you publish it instead of abusing the shit out of it?

Explain?

Are all problems solvable efficiently by a computer?

Is the subset of efficiently solvable problems NP equal to all possible problems, P?

It's like..
There are great composers like Mozart, Bach, etc.
Can everyone else be a great composer by simply listening to their compositions without formal training?

That's a shitty analogy and you should feel bad

>>>/google/

P is not the class of every possible problem
P is the class of every problem that can be solved deterministically in polynomial time
NP is the class of problems that can be solved non-deterministically in polynomial time
To solve an NP problem deterministically, right now, you need exponential time, which is why current encryption algoruthms are good
If you discover that P = NP then you can solve all NP problems in polynomial time

Yes, if P = 0 or N = 1.

It's worth noting
Still requires us to find the algorithm that can accomplish it. All P=NP would tell us is that such an algorithm exists.

Like mozart, P = NP will probably be with us forever.

The non tech way to see it is, there are problems that are easy to solve (P) and some that are easy to check (NP).
For example finding a number equal to K in some array is in P, that's O(N). Now finding a subset of numbers that add up to K is in NP, if I give you the indexes of the numbers is easy to check in O(N) if such answer is correct, but it may take exponential time to find them.
This is why NP problems are "Those that a non-deterministic turing machine can solve in polynomial time", since it may randomly stumble upon those numbers and check them in polynomial time. Luckily there is a possibility that it will always find the answer in polynomial time, which doesn't happen in a deterministic one.
It is obvious from above that P is inside NP, nobody knows if the opposite is true.

vs

I'm not even sure how you'd do the first one.

This is my understanding of it. I might be wrong.

Bruteforcing RSA in a reasonable amount of time is a NP problem. All NP problems (which includes all NP-complete problems) can be reduced to any NP-complete problem. This means that if you find a fast algorithm for one NP-complete problem (say, traveling salesman) you can take a RSA public key you want to derive the private key from and convert it into a traveling salesman problem that you can then quickly solve to get the private key.

If you have a way to break RSA you can log into servers that use SSH keys, or impersonate bank websites, or make a fuckton of money from rich groups like the NSA who want to decrypt things.

You are right, I forgot about the proof of existence vs actual existence

An intuitionist would tell you that proving P=NP is the same as having an algorithm for solving all NP problems in polynomial time.


In constructive mathematics, that's one and the same.

Banks and others would quickly react defensively. You'd have to be really careful to get away with it for long.

go to learn some computer science, you uneducated faggot

Yes, for N = 1 or N = 0

You said the same thing as except you said it wrong

Next to no cryptosystems are provably based on a provably NP-complete problem and the ones that were have been broken because it doesn't suffice to have a hard problem in the worst case — you need a hard problem in the average or even best case. Check out Merkle-Hellman for an example of this. The theoretical basis of most cryptography is pretty wonky, especially hash functions.


Fuck off constructivists, you just want to take my choice away.

Fuck me, I can't read and mixed two posts together.

what if there is a neet somewhere who has solved it and p = np but neet so he just sitting on it because rules 1 & 2 and occasionally uses it to steal games on steam and bitcoins from exchanges to buy mountain dew and doritos?

...

Your pepe has been submitted and is pending review. If all goes well, you should see it in the next issue!

-The Editors at Theoretical Computer Science Journal

You mean like Fermat's theorem?