can someone explain to me, in layman's terms, P vs. NP
- Thread starter Blaze500
- Start date
P is the set of problems that can be solved fairly quickly by a computer and their answers can be verified quickly (i.e. in polynomial time). NP refers to the set of problems where possible solutions can be checked quickly, but take a prohibitively long amount of time to be actually be solved by a computer for all but the smallest input sizes.
The P = NP problem basically comes down to this question:
"If the answer to a problem is easy to check, is the problem itself easy to solve?"
In other words, it asks if NP problems, which we already know we can quickly check whether answers to them are correct or not, are actually P problems and we simply haven't found polynomial time solutions to them yet.
If you ever take a theoretical computer science course, this topic will definitely come up at some point, likely whenever the subject of computational complexity theory comes up
The P = NP problem basically comes down to this question:
"If the answer to a problem is easy to check, is the problem itself easy to solve?"
In other words, it asks if NP problems, which we already know we can quickly check whether answers to them are correct or not, are actually P problems and we simply haven't found polynomial time solutions to them yet.
If you ever take a theoretical computer science course, this topic will definitely come up at some point, likely whenever the subject of computational complexity theory comes up
do you think this will ever be solved?
Type Username Here
Not a new member
Quantum computing may be our only hope to even come close.
so this is something that would even be more groundbreaking then Einstein's General Relativity if solved
Type Username Here
Not a new member
fukk no. Not even close.
I'm not sure. The majority of CS researchers think the answer is P != NP, but no one's proven it one way or the other.
Ehhh, I don't know if I'd say that. But if someone did prove that P = NP, it'd basically result in a revolution in computing.
For example, much of our modern cryptography would probably have to be tossed in the bushes if this were the case, because much of it relies on the fact that currently, factoring huge numbers happens to be an NP problem
and if I'm correct, to find out if P=NP we have to use "Turing Machines" which i dont know if Alan Turing actually created them, weren't they more of a thought experiment he did?