• Intractable problems are problems with high complexity and hence difficult to change and resolve.

• Such problems are very difficult for the computers to solve due to complexity issues.

• The complexity also depends on the number of steps needed to resolve them.

• Based on the number of steps the classification is done as P-Problems, NP-Problems and NP-Complete Problems

1. P-Problems :

• Here, the number of steps needed to resolve the problem relates polynomial to the input size.

• It is given by the expressions such as $O(n^2)$, $O(n^9)$, or in general as $O(n^c)$, where c is a constant, but not $O(2^n)$ or $O(n!)$

• Problems solvable in polynomial time using a Deterministic Turing Machine come in this category of classes.

2. NP-Problems :

• Problems solvable in polynomial time using Non Deterministic Turing Machine fall in this category

• A Non Deterministic Turing Machine is a Deterministic Turing Machine with two stages of processing – guessing and checking

• Guess: - It guesses a solution then writes it to the tape.

• Checking :- Evaluates whether the guess solves the problem or not

• The number of guesses solutions can either be polynomial or exponential

• If number of guesses solutions are polynomial, Non Deterministic and Deterministic Turing Machines are equivalent

• This class includes problems that can be solved in exponential time wrt input size.

• A typical example can be the Travelling Salesman Person(TSP)

3. NP-Complete:

• A problem P is NP-Complete if a. P is in NP

  b. For every problem L in NP, there is a polynomial time reduction from L to P.

• Given below is the NP-Complete problems family tree