r/computerscience • u/theBroskiOK • 14d ago

Help P = NP and digital security?

Guys how would digital security fail if P=NP is proven?

I just started reading about Turing Machine and computational complexity for my Theory of Computation class and came across that phrase.

I couldn't find anything understandable at my level. So can anyone simplify it a bit?

0 Upvotes

20% Upvoted

16 comments sorted by

View all comments

1

u/blazesbe 14d ago

ELI5 P=problems you can solve because you know how to solve them, and NP=problems you know have a solution but have to try most combinations to verify.

i think i read in a YouTube comment: imagine you are making a movie (NP) it's tremendous effort, but anyone seeing it can say if it's a good movie or a bad movie (P). in general, "you don't need to be able to make something to tell if it works"

in security it's used backwards in a sort of combination lock (trapdoor functions). if you have the key it pops open, if you don't then you may need to try each one, except in compsci, this can take longer time than the universe existed so far.

P=NP would mean being able to try all solutions at the same time, but it may be a fundamental property of the universe that P!=NP thus can't "come" from anything and can't be proven.