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 find a problem that a given algorithm will solve. For instance, you may pose a decision problem if an array is sorted. You can either scan over it and verify elements appear in ascending order, or you may just run the fastest sorting algorithm on a copy of the array and compare the result with the given array.

• Multiplication can be solved in polynomial time. The decision version of the problem will be if we multiply x and y, is the result z? We will simply multiply x and y and compare the product with z.
• Finding the greatest common divisor is also a problem in the P class.
• Is a given string S a palindrome? This decision problem can be solved in polynomial time.
• Given two strings p and q, is p a substring of q?

Problems solved on whiteboards during interviews can be either algorithms or decision problems. Sorting, binary search, tree traversals are all polynomial time algorithms but not decision problems. Whenever talking about problems in complexity classes, we are referring to decision problems. So if you state that selection sort is in complexity class P, your statement isn’t valid. However, the algorithm can be run in polynomial time to answer a decision problem that insertion sort solves, and that decision problem would be considered to be in P.