mgroves

One of the concepts central to computer science is the question of P vs NP. P is the set of all problems solvable in deterministic polynomial time. Algorithms that are O(n^k) are in P, for instance. NP is the set of all problems solvable in nondeterministic polynomial time. Algorithms that are O(kⁿ) are in NP, for instance (k is a constant in both cases). Many artificial intelligence algoritms are NP. We know that P is a subset of NP, since anything in deterministic time can easily be converted to a nondeterministic problem. We don’t know if P is a proper subset of NP, or rather, if P = NP or not. This is actually one of the famous “Millennium” math problems with a million dollar bounty. I’ve found a very simplified and accessible explanation of the problem at VB-helper of all places.

I find the subject fascinating, because an eventual proof one way or another would be quite significant. If someone were to prove that P=NP, for instance, a lot of cryptography would become useless, but applied AI would vastly improve.

See also: NP-complete