In this chapter, we introduce the theory of intractability, that is, discuss whether a problem can be solved in polynomial time or not, that is, P, Non-deterministic Polynomial (NP) Problems are discussed. The classification of problems into NP-hard problems and NP-complete (NPC) problems is explained with examples.
The subject of computational complexity theory is focused on classifying problems by how hard they are. There are many different classifications depending on the time taken by the problem. The following are the types of classification.