0
Explain Intractable problems and their classification in detail

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

0  upvotes
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

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More