Question: Explain Intractable problems and their classification in detail
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
0
  • 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

ADD COMMENTlink
written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.