We know that Touring Machine is something which possess the most power of computation. Now our task is to separate problems in different complexity class to identify their complexities.
We can take problems as per 3 version.
1. Optimization
2. Decision
3. Searching
For example this problem :-
Graph vertex Coloring (G(V,E),F) :-
Given a simple un-directed graph with vertex set V and edge set E and we have to assign color vector F = (fv) of size |V| where fv represent color of vertex v and for any two vertex the having an edge in between can't have same color.
Optimization version :- Report the min value of max(f0,f1,....f(|V|-1)) we can ever make.
Searching version :- Report the F for which max(f0,f1,....f(|V|-1)) will be minimum
Decision version :- Report whether a given assignment F is a minimal assignment found by serching
For the complexity analysis we are going for the Decision version.
We will classify the problems as NL , P , NP, PSPACE, EXPTIME,EXPSPACE and so on...
Let's see them one by one .
We can take problems as per 3 version.
1. Optimization
2. Decision
3. Searching
For example this problem :-
Graph vertex Coloring (G(V,E),F) :-
Given a simple un-directed graph with vertex set V and edge set E and we have to assign color vector F = (fv) of size |V| where fv represent color of vertex v and for any two vertex the having an edge in between can't have same color.
Optimization version :- Report the min value of max(f0,f1,....f(|V|-1)) we can ever make.
Searching version :- Report the F for which max(f0,f1,....f(|V|-1)) will be minimum
Decision version :- Report whether a given assignment F is a minimal assignment found by serching
For the complexity analysis we are going for the Decision version.
We will classify the problems as NL , P , NP, PSPACE, EXPTIME,EXPSPACE and so on...
Let's see them one by one .
No comments:
Post a Comment