Computational Complexity Classes PDF

Unit II Computational Complexity Classes Reference for this presentation is Horowitz and Sahani, "Fundamentals of Computer Algorithms", 2nd edition. Galgotia publication,, 2008, ISBN: 978 81 7371 6126 Computational Complexity Classes ❖ Basic Concepts of Compl...

Unit II Computational Complexity Classes Reference for this presentation is Horowitz and Sahani, "Fundamentals of Computer Algorithms", 2nd edition. Galgotia publication,, 2008, ISBN: 978 81 7371 6126 Computational Complexity Classes ❖ Basic Concepts of Complexity Classes ❖ Non Deterministic Algorithms ❖ P and NP , NP Hard and NP Complete ❖ Clique decision problem ❖ Node cover decision problem ❖ Directed hamiltonian cycle problem ❖ Satisfiability problem ❖ Travelling salesman problem ❖ NP Hard Problems Problems and Their Classes Solved many problems using different algorithms For each problem - algorithm and computing time Problem classes based on computing time of best known algorithm ✈ P class ✈ NP Class P Class This group consist of all problem whose computing time are polynomial time Computing time is bounded by polynomials of small degree ✈ Insertion sort O(n2) ✈ Merge and Quick sort O(n logn) ✈ Binary search O(log n) ✈ Linear Class ✈ Quadratic and Cubic Class Also called as tractable (easy) problems NP Class Computing of best known algorithm are non polynomial TSP using dynamic programming O(n2 2n), Knapsack O(2 n/2) No one was has been able to develop a polynomial time algorithms for this class problems Requires vast amount of time to execute even moderate size problems Problems that can be solved using super polynomial, exponential time algorithm are called intractable (Hard ) Deterministic and Non Deterministic Algorithms Deterministic Algorithm ✈ Result of every operation is uniquely defined ✈ Agree with way programs are executed on a computer In a theoretical framework we can remove this restriction on the outcome of every operation Non Deterministic Algorithm ✈ Allow algorithm to contain operations whose outcomes are limited to specific set of possibilities ✈ Machine executing such operations are allowed to choose any one of these outcome subject to termination condition defined ✈ This leads to non deterministic Algorithm Non Deterministic Algorithms Introduce new functions ✈ Choice (set S) – arbitrarily choose one element of S ✈ Failure() – signals an unsuccessful completion ✈ Success()- signals a successful completion ✈ X = choice(1,n) results in x being assigned any one of integer in the range of 1 to n, but no rule how this choice is to be made ! Failure and success – just to define a computation of algorithm and cannot be used to effect a return Whenever there is a set of choices that leads to a successful completion, then one such set of choices is always made and algorithm terminates successfully Non Deterministic Algorithms NDA terminates unsuccessfully if and only if there is no set of choices leading to success signal Hence depending upon order in which choices are made – affects the successful / unsuccessful termination of NDA Computing time of Choice(), Success(),failure() is O(1) – Constant Machine capable of handling NDA is called as nondeterministic Machine (NDM) Although, NDM do not exist in practice, there are certain problems that can not be solved by deterministic algorithm. Non Deterministic Search Algorithms A decision problem gives answer either 0 or 1 Search a element x in a given set A, write index else 0 ✈ J = choice (1,n); // Select form a set ✈ If A[j] = x then {write (j);success();} //write index ✈ Write(0); failure(); Computing time of this algorithm is O(1) in both cases , HOW ? Any Deterministic search algorithm requires O(n) time – Linear  Non Deterministic Sorting 1. Algorithm Nsort(A,N) In the for loop of 5 to 10 each A[i] is assigned to position in B 2. // sort n positive numbers Line 7 non deterministically 3. { identifies this position 4. For I = 1 to n do B[i] = 0 ; // Line 8 checks whether this position is initialize B already used or not ! 5. For I = 1 to n do The order of numbers in B is some 6. { permutation of the initial order in A 7. J = choice(1,n); For loop of line no 11 and 12 verifies 8. If B[j] != 0 then failure(); the B is in ascending order, 9. B[j] = A[i]; Since there is always a set of choices 10. } at line no 7 for ascending order, this is 11. For I = 1 to n-1 do // verify the order a sorting algorithm of Complexity 12. If B[i] > B[i+1] then failure (); O(N) 13. Write (B); All deterministic sorting algorithms must have A complexity O(nlogn) 14. Success(); 15. } Non Deterministic Algorithms A deterministic interpretation of a non deterministic algorithm can be made by allowing unbounded parallelism in computation Each time a choice is to be made, the algorithm makes several copies of itself One copy for each possible choices, many copies are executing at the same time. First copy to reach successful completion terminates all other copies If a copy reaches to failure completion then only that copy of algorithm terminates This interpretation enable us to better understand NDA Non Deterministic Machine NDM does not makes any copies of an algorithm every time choice is made NDM has ability to select a correct element from set of choices (if exists) A correct element is defined relative to a shortest sequence of choices that leads to successful completion If no sequence of choices leading to successful termination then unsuccessful termination / computation with one unit of time Machine is Fictitious, no concerns with how the machine can make a correct choice at each step NPC Theory Does not provide a method of obtaining polynomial time algorithm for problems of NP Class Nor it say that algorithms of polynomial complexity do not exist But many of the problems for which there are no known polynomial time algorithms are computationally related Further Classes of Problems NP Complete (Non deterministic polynomial time complete) problems – NPC Problem can be solved in polynomial time if and only if all other NPC problems can also be solved in polynomial time NP Hard problems – if NP hard problem can be solved in polynomial time , then all NPC problems can be solved in polynomial time No NPC or NPHard problem is polynomially solvable All NP Complete problems are NP hard but some NP Hard are not NPC  There are many problems of NPC and NPH , focus should be on nondeterministic computations (to be defined) Relationship of these classes to nondeterministic computations together with apparent power of nondeterminism leads conclusion no NPC or NPH is polynomially solvable Definitions Decision problem - a problem having the answer either 0 or 1. Decision problem can be NPC Decision Algorithm – solves a decision problem. Gives output 1 on successful completion and 0 on unsuccessful termination Optimization Problem – problem involving the identification of an optimal value (either maximum or minimum) for a given cost function. Optimization problem may be NP Hard Satisfiability problem – find out whether a given expression is true for some assignment of truth values to the variable in that expression Definitions Clique – Complete subgraph for a given graph, size of Clique is the number of vertices in subgraph Reducibility – Let L1 and L2 are 2 problems. L2 can be solved in polynomial time using a deterministic algorithm. If the same algorithm can solve problem L1 in deterministic polynomial time, then L1 α L2 (L1 Reduces to L2) α is a transitive relation NDA It is possible to construct NDA for which many different choices lead to completions. Ex. If numbers of Array A are equal , many different permutations will result in sorted sequence. Concern with NDA that generate unique output Successful completion if output 1 Output 0 if no sequence of choices leading to a successful completion. Output statements are implicit in signals success and failure  Idea of decision algorithm may appear very restrictive but, many optimization problems can reformed into decision problems with property ✈ Decision problem can be solved in polynomial time if and only if the corresponding optimization problem can In other cases, we can at least make statement that if the decision problem cannot be solved in polynomial time then the optimization problem cannot either. Maximal Clique A maximal complete subgraph of a graph G(V,E) is clique. Size of clique is the number of vertices in it. Max Clique problem is an optimization problem that has to determine the size of largest Clique in G Corresponding decision problem is to determine whether G has a clique of size at least k for some give k. Maximal Clique – Decision Problem Let Dclique(G,k) be a deterministic decision algorithm for the Clique decision problem Size of max clique can be found by different values of k K = n, k= n-1, k= n-2 ,…. Until Dclique output = 1 If time complexity of Dclique = f(n) then size of max clique can be found in time