P is the set of all problems that can be solved in polynomial time. This is, the problem of "How many apples are on the table?" is in P, because you can figure out how many apples there are by using O(n) (that's Big-oh notation!) steps, where n is the number of apples. P is contained within (and is possibly equal to) the NP complexity class. No one knows for sure if all problems in NP can be solved in polynomial time. However, it has been proven that if anyone ever finds an NP-Complete problem (a problem in the NPC complexity class) that can be solved in polynomial time, then ALL NPC problems can be solved in polynomial time.

Log in or registerto write something here or to contact authors.