P and NP classes

P - Polynomial Time Problems

The P stands for polynomial time. Problems which can be solved in n^k, where k is some constant from the set of natural numbers ( 1, 2, 3 ...), lie in the complexity class P. More simply, problems to which we can find solutions in polynomial time belong to the complexity class P. Note that when we say problems we are talking about decision problems. All the problems in P are decision problems. Strictly speaking, algorithms such as sorting, binary search, and tree-travels are algorithms that can be used to solve decision problems. However, we can always ...