Introduction Figure 1: Relation between P, NP, NP Complete and NP Hard problems In this blog we are going to discuss about the types of problems in computer science like P, NP, NP Hard, NP Complete and the solution to P vs NP. Each term is explained in detail and in an easy to understand way. So let’s dive deep into the topic ! P Problems P (polynomial) complexity class basically contains all the problems that can be solved by a deterministic Turing machine in polynomial time (for example: O (n), O (n 2 ) and so on). An algorithm is said to be solvable in polynomial time if for some k>0, its running time on input size of n is O ( n k ). The algorithms with exponential running time are not polynomial. Which problems fall under P complexity class? 1. Recognizing Palindrome The problem of recognizing palindromes is sol vable in linear time, which is polynomial time. To decide if x is a palindrome, just reverse x and check whether the reversal of