Decision Problems

Decision Problem
Many optimization problems can be formullated as Decision problem
-Decision problem is YES/NO question.The question is about some input.
      It has two parts --
1)Instance Description-This part contains input specified in the problem.
2)Question Part-This is YES/NO question.
                        -The question is about input specifies in the instance description.
Eg.  P1
     Given a graph G(V,E)
           QUESTION- Is graph G is m Colourable.
  
       P2
      Given a graph G & integar m.
            QUESTION-Is graph G is m Colourable.

Let the solution of the given Decision problem is given by function θ(m^2.N^m)


Its clear from the function that problem can be solved in polynomial time whereas P2 goes into exponential time.