**1 Answer**

written 5.3 years ago by |

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