Explain Intractable problems and their classification in detail
intractable problems • 1.6k  views
  • 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

enter image description here

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more