Lower bound theory Np hard & Np completeness

Unit 5 BTech pbl project python

1. UNIT-5 LOWER BOUND THEORY NP HARD & NP COMPLETENESS

2. Lower Bound Theory Lower Bound, L(n), is a property of the specific problem, i.e., sorting problem, MST, matrix multiplication, not of any particular algorithm solving that problem. Lower bound theory says that no algorithm can do the job in fewer than L(n) time units for arbitrary inputs, i.e., that every comparison based sorting algorithm must take at least L(n) time in the worst case. L(n) is the minimum over all possible algorithms, of the maximum complexity.

3. Comparison trees In a comparison sort, we use only comparisons between elements to gain order information about an input sequence (a1; a2......an). Given a i ,a j  from (a 1 , a 2 .....a n )We Perform One of the Comparisons a i  < a j        less than a i  ≤ a j        less than or equal to a i  > a j        greater than a i  ≥ a j        greater than or equal to a i  = a j        equal to

4. To determine their relative order, if we assume all elements are distinct, then we just need to consider a i  ≤ a j  '=' is excluded &, ≥,≤,>,< are equivalent. Consider sorting three numbers a1, a2, and a3. There are 3! = 6 possible combinations: (a1, a2, a3), (a1, a3, a2),   (a2, a1, a3), (a2, a3, a1)   (a3, a1, a2), (a3, a2, a1)  

5. The Comparison based algorithm defines a decision tree. Decision Tree:  A decision tree is a full binary tree that shows the comparisons between elements that are executed by an appropriate sorting algorithm operating on an input of a given size. Control, data movement, and all other conditions of the algorithm are ignored. In a decision tree, there will be an array of length n. So, total leaves will be n! (I.e. total number of comparisons) If tree height is h, then surely

6. n! ≤2 n (tree will be binary ) Taking an Example of comparing a1, a2, and a3. Left subtree will be true condition i.e. a i  ≤ a j Right subtree will be false condition i.e. a i  > a j

7. Polynomial & Non-polynomial Time Algorithms The algorithms are mainly classified into two categories based on their time complexities: Polynomial time algorithms O(p(n)), where p(n) is a polynomial on n : O(n 2 ), O(n 3 ), O(1), O(n lg n) and Non-polynomial time O(2 n ), O(n n ), O(n!) algorithms. A problem that can be solved in polynomial time in one model can also be solved in polynomial time in another model. The classes of polynomial time solvable problems are closed under addition multiplication and composition. The computing time of non-polynomial are greater than polynomial. It is difficult to develop the algorithms whose time complexity is polynomial for non-polynomial time problems.

8. NP HARD AND NP COMPLETE Polynomial time Exponential time Linear Search-n 0/1 Knapsack -2 n Binary Serach -log n Travelling SM- 2 n Insertion sort-n 2 Sum of subsets- 2 n Merge sort- nlogn Graph Coloring- 2 n Matrix multiplication- n 3 Hamiltaneon Cycle- 2 n

9. Deterministic & Non-deterministic Algorithms In any algorithm, if every operation is uniquely defined, then it is called a deterministic algorithm . If the operations are not uniquely defined, but are limited to specified set of possibilities, such algorithms are called non-deterministic algorithms . NP stands for “Nondeterministic Polynomial-time” The deterministic algorithms are a particular case of non-deterministic algorithms. Since deterministic algorithms are special case of non-deterministic algorithms.

10. Deterministic & Non-deterministic Algorithms “ P ” denotes the set of all decision problems solvable by a deterministic algorithm in polynomial time. “ NP ” denotes the set of all decision problems solvable by non-deterministic algorithm in polynomial time. so we can conclude that P is subset of NP. P  NP P NP

11. Non-deterministic Algorithms To specify non-deterministic algorithms we use the following three functions: Choice (s) : Arbitrarily chooses one of the elements of set S Failure : Signals an unsuccessful completion. Success : Signals are successful completion. A non-deterministic algorithm terminates unsuccessfully if only if there exists no set of choices leading to a success signal. Whenever there is set of a choices that leads to success signal the algorithm terminates successfully. In case, successful completion is not possible then the time complexity is O(1). In case of successful signal completion then time required is the minimum number of steps needed to reach a successful completion O(f(n)).

12. Tractable and Intractable Problems Problems that can be solvable in a reasonable(polynomial) time are called tractable problems Some problems are intractable, as they grow large, we are unable to solve them in a reasonable time. are treated as Intractable problems. All deterministic polynomial time algorithms are tractable and the non-deterministic polynomials complete (NP-complete) are intractable .

13. Sorting algorithm as Non-deterministic algorithm Example : Let A[I], 1 < n be an unsorted set of positive integers. B(1: n) is an auxiliary array. The Non-deterministic algorithm NSORT (A, n) sorts the numbers into non-decreasing order. Time complexity is O(n) NSORT( A,n ) B ← 0 for I← 1 to n {j ← choice (1:n) if(B[j] =/ 0) then failure endif B[j] ← A[I] } for I ← 1 to n-1 { if (B[I] > B[I+1]) then failure endif} print (B) STOP

14. Example: A non-deterministic algorithm for searching for an element x in the given set of elements A[1:n] with time complexity O(1) j ← choice (1: n) if (A[j] = x) then {print j; success} else { print (0) failure}

15. What is Satisfiability ? Satisfiability is to determine whether a Boolean formula is true for some assignment of truth values to the variables. The Boolean formula can be constructed using the following literals and operations. A literal is either a variable ( x i ) or its negation (  x i ) The literals are connected with operations ^ (and) , v (or), Parentheses: Left & Right parenthesis ( , ). A Boolean formula is in Conjunctive Normal Form iff it is represented by ^ C i , where C i is the i th clause represented with literal l j , l j is the j th variable. If each clause has exactly three distinct variables in the CNF then the boolean formula is said to be in 3-CNF. Example: C 1 ^ C 2 ^ C 3 ^ C 4 = (x 1 vx 2 v  x 3 ) ^ (x 1 v  x 2 vx 3 ) ^ (x 1 vx 2 vx 3 ) ^ (  x 1 vx 2 vx 3 )

16. Circuit Satisfiability A Boolean combinational circuit composed with the AND, OR, and NOT gates is said to be circuit satisfiabil ity

17. 3-CNF

18. Reducibility A problem L 1 can be reduced to another problem L 2 if any instance of L 1 can be easily rephrased as an instance of L 2 and the solution to the problem L 2 provides a solution to the instance of L 1 . Then the problem L 1 is reducible to L 2 . Note: L 1 < L 2 or L 1 < p L 2 denotes that the problem L 1 can be solved by a polynomial time algorithm reduces to L 2 that solves also in polynomial time. If two problems L 1 & L 2 are said to be polynomial equivalent if and if L 1 ≤ L 2 and L 2 ≤ L 1 . The reducibility satisfies that transitive relation, that is, if L 1 < L 2 and L 2 < L 3 then L 1 < L 3 . If L 1 < p L 2 then L 1 is not more than a polynomial factor harder than L 2 , (which is why the “Less then or equal to” notation for reduction).

19. (a) Reducible to (b) (Taking complementary graph)

20. NP-HARD AND NP-COMPLETENESS NP-HARD: If R is polynomial-time reducible to Q, we denote this R < p Q . If all problems R  NP are polynomial-time reducible to Q, then Q is NP-Hard. A problem L is said to be NP-HARD if and only if satisfiability reduces to L. NP-COMPLETE: A Problem L is said to be NP-Complete if an only if . L is NP hard and L belongs to NP. We say Q is NP-Complete if Q is NP-Hard and Q  NP

21. Relationships Between P, NP, NP-Hard & NP –Complete P: sets of decision problems that are solvable in Polynomial time by using Deterministic algorithms. NP: sets of decision problems that are solvable in Polynomial time by using Non-Deterministic algorithms. NPH: sets of decision problems that are solvable in Polynomial time by using NP Hard NPC: sets of decision problems that are solvable in Polynomial time by using NP-Complete problems. P  NP; P = P  NP; NP = P  NP NPC = NP  NPH NPC  NP NPC  NPH

22. Cooks Theorem Statement : Satisfiability is in P iff P=NP. Proof: Let I be the set of inputs of length ‘ n ’. Let A be a non-deterministic algorithm whose time complexity is polynomial O( P(n) ) , where ‘n’ is the size of the input ‘I’. Let Q(A,I) be the Boolean formula constructed for the non-deterministic algorithm A with an input set I. Q is satisfiable if an only if the algorithm A has a successful termination with the input I of size n. Then the time complexity of Q(A,I) will be O( P 3 (n) log n ) = O( P 4 (n) ).

23. Contd …. Let B be a deterministic algorithm used to determine the outcomes of the non-deterministic algorithm A . If O(q(m)) is the time required to determine if a formula of length m is satisfiable, then the complexity of B is O( q ( P 3 (n) log n ) + P 3 (n) log n = O(q(P 4 (n))) if B computes Q. The complexity of B becomes O(r(n)) for some polynomial r(.). Hence if satisfiability is a in P then for every non-deterministic algorithm A, we have a deterministic algorithm B in P. So, if satisfiability is in P iff P = NP

24. Statements of Decision Problems Hamiltonian Decision Problem : Any graph G is said to Hamiltonian Graph if there exists a path such that we can traverse each vertex exactly once along the edges and can also visit the starting vertex then such a closed path is called an Hamiltonian cycle. Chromatic Number Decision Problem: Consider a graph G(V,E) can you paint the vertices of graph with minimum number of colors such that the adjacent vertices colors differ. The minimum number of colors required for G is called the chromatic number of the graph.

25. Max Clique Decision problem: Let G be a non directed graph consisting of a set of vertices V and a set of edges E. The clique problem is an optimization problem of finding a maximal number of vertices complete sub-graphs of G. As a decision problem, we can express as whether a clique of a given size to K exists in the Graph. Node Cover Decision Problem: Let G (V,E) be a non-directed graph. A set S, V is a node cover if all edges in E are incident to it. The size of a vertex cover is the number of vertices in it. The Vertex cover problem is to find a vertex cover of minimum size in a given graph. Example : Find the minimum size of the node cover to the following graph. Vertex set {S, 4} touches all edges in G. The size of node cover for G is 2.

26. Sum of subsets problem: Suppose we are given n distinct positive numbers and we desire to find all combinations of these numbers whose sum is m. This problem is called a sum of subsets problem. Example: Let W = (5,10, 12,13, 15, 18) be the vector of six distinct numbers. Find all combinations of these numbers whose sum is m =30. Let xi be the I the weight decision each xi takes the values 0 or 1 (selecting the I weight or not selecting the i th weight). Then we can express it as The different possible solutions are (1,1,0,0,1,0) : (5 10 15) (1,0,1,1,0,0) : (5 12 13) (0,0,1,0,0,1) : (12 18)

27. NP- Complete problems Hamiltonian cycle problem is NP-complete. Max clique decision problem is NP-complete. Node cover decision problem is NP-complete Graph Colouring problem is NP-complete Satisfiability problem is NP-complete

28. Clique D ecision Problem(CDP) A clique in an undirected graph refers to a fully connected sub-graph inside the same graph. A complete sub-graph is a sub-graph in which every vertex is linked to every other vertex. The Max-Clique issue is a computer problem that involves finding the largest possible clique in a given graph. The concept of a maximum clique is applicable to several real-world challenges. For example, a social networking application in which vertices represent individual profiles and edges indicate mutual friendships in a graph. Within this network, a clique is a distinct group of individuals that possess mutual knowledge of one another. In order to identify a maximum clique, it is possible to methodically examine all subsets. However, this type of exhaustive search is excessively time-consuming for networks that consist of more than a few dozen vertices.      

29. Max-Clique Algorithm The algorithm to find the maximum clique of a graph is relatively simple. The steps to the procedure are given below − Step 1: Take a graph as an input to the algorithm with a non-empty set of vertices and edges. Step 2: Create an output set and add the edges into it if they form a clique of the graph. Step 3: Repeat Step 2 iteratively until all the vertices of the graph are checked, and the list does not form a clique further. Step 4: Then the output set is backtracked to check which clique has the maximum edges in it. Example Here, the sub-graph containing vertices 2, 3, 4 and 6 forms a complete graph. Hence, this sub-graph is a  clique . As this is the maximum complete sub-graph of the provided graph, it’s a  4-Clique .

30. Node Cover decision problem: A vertex-cover of an undirected graph  G = (V, E)  is a subset of vertices  V '   ⊆ V  such that if edge  (u, v)  is an edge of  G , then either  u  in  V  or  v  in  V '  or both. Find a vvertex coverof maximum size in a given undirected graph. This optimal vertex cover is the optimization version of an NP-complete problem. However, it is not too hard to find a vertex-cover that is near optimal. Example The set of edges of the given graph is − {(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}      

31. Now, we start by selecting an arbitrary edge (1,6). We eliminate all the edges, which are either incident to vertex 1 or 6 and we add edge (1,6) to cover. In the next step, we have chosen another edge (2,3) at random

32. Now we select another edge (4,7). We select another edge (8,5). Hence, the vertex cover of this graph is {1,2,4,5}. Analysis It is easy to see that the running time of this algorithm is  O(V + E) , using adjacency list to represent  E ' .