P vs. NP and the Computational Complexity Zoo
When Grade-A nerds get together and talk about programming and math, a popular topic is P vs NP complexity. There’s a lot to P vs NP, but boiled down to its essence, according to the video:
Does being able to quickly recognize correct answers [to problems] mean there’s also a quick way to find [correct answers]?
Most people suspect that the answer to that question is “no”, but it remains famously unproven.
In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer.
Stay Connected