{"id":142,"date":"2018-07-19T06:52:37","date_gmt":"2018-07-19T06:52:37","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=142"},"modified":"2018-07-19T06:58:53","modified_gmt":"2018-07-19T06:58:53","slug":"overview-of-np-complete-problems","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/overview-of-np-complete-problems\/","title":{"rendered":"Overview of NP-Complete problems"},"content":{"raw":"
\r\n

This module 33 focuses on NP-Complete problems. The module also discusses about Class P and NP problems. This module also introduces the theory of NP-Complete problems. The objectives of this module are<\/p>\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the P and NP Class\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand NP-Complete problems\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To know some NP-Complete problems\r\n\r\n \r\n\r\nComputational Complexity<\/strong>\r\n\r\n \r\n

There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory [2,3].<\/p>\r\n \r\n

Algorithmic complexity theory [3,4] aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number<\/strong> n<\/em> is defined to be the number of binary bits needed to write n. For example,<\/em> Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.<\/p>\r\n \r\n

Asymptotic Analysis <\/strong>[1,2] refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.<\/p>\r\n \r\n

Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm.\u00a0In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds <\/span>defines the limits of the algorithm. Upper bound indicates the worst case performance of the algorithm and lower bound indicates the best case performance of the given algorithm.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nSolvability of Problems<\/strong>\r\n\r\n \r\n\r\nA problem is solvable<\/em> if there exists a program that always terminate and gives the answer.\r\n\r\n \r\n\r\nSolvability of the problems is related to the tractability of the problem [2,3].\r\n\r\n \r\n

A problem is tractable<\/em> if it is solvable and we can say Time(x)\u2264(some polynomial).<\/em> The problems that can be solved using run time less than polynomial is called polynomial time algorithms.<\/p>\r\n \r\n\r\nClass P Proble ms<\/strong>\r\n\r\n \r\n

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. A problem is feasible if it has a solution cost as a polynomial. All problems that can be solved in polynomial time is called polynomial time or class P problems. Some of the examples of Class P problems are<\/p>\r\n \r\n\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Searching\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Element uniqueness\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph connectivity\r\n\r\n \r\n

Polynomial time algorithms also give a notion of efficient algorithms. All polynomial time algorithms are efficient algorithms as the problem can be solved. How about O(n log n)? or O(n2) ? yes. These algorithms are polynomial algorithms and hence solvable. On the other hand, the algorithms having complexity like O(2n) or O(n!) are not polynomial algorithms and instead are called exponential algorithms as these functions are not polynomial and whose growth is exponential and hence cannot be solved for larger instances.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nWhat is NP Class?<\/strong>\r\n\r\n \r\n\r\nThe class of decision problems that can be solved by a non-deterministic polynomial algorithm is called class NP problem.\r\n\r\n \r\n

What is a Non-deterministic algorithm? Non-deterministic algorithms produce an answer by a sequence \u201cGuesses\u201d while deterministic algorithms (like those that a computer executes) make decisions based on information.<\/p>\r\n \r\n\r\n \r\n\r\nSome of the examples of NP problems are given as follows:\r\n

    \r\n \t
  • \u00a0 Traveling Salesman<\/li>\r\n \t
  • \u00a0 \u00a0N-Queens<\/li>\r\n \t
  • \u00a0 Classroom Scheduling<\/li>\r\n \t
  • \u00a0 \u00a0Packing<\/li>\r\n \t
  • \u00a0 \u00a0Scheduling<\/li>\r\n<\/ul>\r\n \r\n

    These problems are hard problems as it is difficult to solve these problems for larger instances. Also, for most of these problems, no polynomial time algorithm is known and also it can be observed that most of these problems are combinatorial optimization problems. Most of the combinatorial problems are hard.<\/p>\r\n \r\n\r\nWhat is a decision Problem?\r\n\r\n \r\n

    A decision problem is a problem whose output is a single Boolean value: YES or NO and NP is\u00a0 the set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.<\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\nOne can conclude that from this discussion that some problems are hard to solve with the following characteristics:\r\n\r\nl\u00a0\u00a0 No polynomial time algorithm is known\r\n\r\nl\u00a0\u00a0 If answer is YES, then it can be checked in polynomial time\r\n\r\nl\u00a0\u00a0 Most combinatorial optimization problems are hard\r\n\r\n \r\n

    Computational complexity is an exciting branch of algorithm analysis that discuss about these issues. The next module discusses about one important class of problems called NP-Complete problems.<\/p>\r\n \r\n\r\n \r\n\r\nCo-NP Proble ms<\/strong>\r\n\r\n \r\n\r\nCo-NP is the opposite of NP. If the answer to a problem in co-NP is NO, then there is a proof of this fact in polynomial time [3].\r\n\r\n \r\n\r\nNP-I Proble ms<\/strong>\r\n\r\n \r\n

    NP-I is called NP- Intermediate problems that are said to be between P and NP. Examples of NP-I problems are factoring problem and graph isomorphism problem.<\/p>\r\n \r\n\r\nWhat is NP-Hard proble m?<\/strong>\r\n\r\n \r\n

    NP-Hard are problems that are at least as hard as the hardest problems in NP. A problem A is NP-hard, if there is a polynomial algorithm exists, It implies polynomial algorithms for every problem in NP. In that case , P = NP whose proof is difficult. Clay Institute announced one million dollar prize in its web site for anyone who gives a proof. It is shown below with the other kinds of problems that are considered difficult (http:\/\/www.claymath.org\/millennium\/)<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Birch and Swinnerton-Dyer Conjecture\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 Hodge Conjecture\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 Navier-Stokes Equations\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 P vs NP\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0 Poincar\u00e9 Conjecture\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0 Riemann Hypothesis\r\n\r\n<\/div>\r\n

    \r\n\r\n7.\u00a0\u00a0\u00a0 Yang-Mills Theory\r\n\r\n \r\n\r\n \r\n\r\nNP-Complete Problems<\/strong>\r\n\r\n \r\n\r\nNP-Complete (or NPC) problems are a set of problems that are well connected. A problem x that is in NP, if any one finds an polynomial time algorithm even for one problem, it implies that polynomial time algorithm for all NP-Complete problems. In other words: Problem x is in NP, then every problem in NP is reducible to problem x. Let us present the overview of NP-Complete Problems\r\n\r\n \r\n\r\n1. Decision Problems<\/strong>\r\n\r\n \r\n

    A decision problem is a problem whose output is a single Boolean value: YES or NO . NP is the\u00a0 set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.<\/p>\r\n \r\n\r\n2. Language Frame work<\/strong>\r\n\r\n \r\n\r\nLet us review some of the important jargons based on [3]\u00a0 now.\r\n\r\n \r\n\r\nAlphabet: An alphabet is a finite set of symbols. For example A = {0,1}\r\n\r\n \r\n\r\nString: A finite sequence of symbols\r\n\r\n \r\n\r\nEmpty String: A string of zero length\r\n\r\n \r\n\r\nLanguage: A set of strings is called a Language\r\n\r\n \r\n\r\nComplementary Language: if the strings are not in L, then it is called complementary Language.\r\n\r\n \r\n\r\n3. Proble m Encoding<\/strong>\r\n\r\n \r\n\r\nThen the decision problem is encoded using Turing machine. Turing machine takes the encoding of the given problem and performs the following actions.\r\n\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If input string is invalid, then Reject\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If input string is valid, but output No, then reject\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If String is valid and output is Yes, then Accept.\r\n\r\n \r\n\r\nOne can summarize this for language L as follows:\r\n\r\n \r\n\r\nP = { L | L is accepted by a deterministic Turing Machine in polynomial time }\r\n\r\n<\/div>\r\n

    \r\n\r\nNP = { L | L is accepted by a non-deterministic Turing Machine in polynomial time }\r\n\r\n \r\n\r\nNP-Complete problem can be formally defined as follows:\r\n\r\n \r\n\r\nQ\u00a0 is an NP-Complete problem iff\r\n\r\n \r\n\r\n1) Q is in NP\r\n\r\n \r\n\r\n2) every other NP problem polynomial time reducible to Q\r\n\r\n \r\n\r\nSo, to prove a problem A is NP-Complete, then reduce a known NP-C problem to A. Hence, reductions are basis of NP-Complete problems.\r\n\r\n \r\n

    NP-Complete problems are solved by non-deterministic algorithms. A non-deterministic algorithm consists of two phases. The first phase is guessing of solutions and the second phase is the verification of the guesses using an algorithm or certificate. If the verification stage of a nondeterministic algorithm is of polynomial time-complexity, then this algorithm is called an NP (nondeterministic polynomial) algorithm [1,2,3].<\/p>\r\n \r\n

    The verification algorithm A has two components. One is input string x and another string called certificate. Certificate is another string y. It takes the input string x, and if A(x,y) = 1 implies the language is verified by the verification algorithm<\/p>\r\n \r\n

    One of the famous NP-Complete problems is Circuit Satisfiability problem. It can be formalized as follows: Given a Boolean circuit, consisting of gates such as, NOT, OR, AND, Is there any set of inputs that makes the circuit output TRUE. Simultaneously, one can check for circuit output NO also.<\/p>\r\n \r\n\r\n \r\n\r\nCook-Levin theore m states that: Circuit- SAT is NP-Complete. [3]<\/strong>\r\n\r\n \r\n\r\n \r\n\r\nThe circuit Satisfiability is formulated mathematically as follows: Given a Boolean formula, determine whether this formula is satisfiable or not.\r\n\r\n \r\n\r\nA\u00a0 literal : xi or -xi\r\n\r\n<\/div>\r\nA clause : x1 v x2 v - x3 \u00ba Ci\r\n\r\n \r\n\r\nA formula : conjunctive normal form\r\n\r\n \r\n\r\nC1& C2 & \u2026 & Cm\r\n\r\n \r\n\r\n \r\n\r\nExample 1: <\/strong>Is there any one assignment that makes the expression true :\r\n\r\n \r\n\r\nx1 v x2 v x3\r\n

      \r\n \t
    • & - x1<\/li>\r\n \t
    • & - x2<\/li>\r\n<\/ul>\r\nSolution:\r\n\r\n \r\n\r\nIt can be observed that the following assignment x1 \u2190 F , x2 \u2190 F , x3 \u2190 T will make the above formula true\r\n\r\n \r\n

      A related problem is called Formula Satisfiability problem. A Boolean formula is in CNF (Conjunctive Normal Form) if it is a conjunction (AND) of clauses. All clauses are disjunction (OR) of many literals. Every literal is a variable or its negation.<\/p>\r\n \r\n

      Another related problem is 3-SAT. In 3-SAT or 3SAT, there must be exactly 3 literals per clause. 3-SAT problem is : Given 3-CNF formula, Is there an assignment that makes the formula to evaluate to TRUE.<\/p>\r\n \r\n\r\n \r\n\r\nExamples of NP Hard Proble ms<\/strong>\r\n\r\n \r\n\r\n \r\n

      Some of the known NP Hard problems are listed here. One of the major NP hard problem is vertex cover.<\/p>\r\n \r\n\r\n(i) Vertex Cover\r\n\r\n \r\n

      Vertex cover is an important problem. It is formally stated as follows: Given a graph G=(V, E), S is the node cover if S \u00cd V and for every edge (u, v) \u00ce E, either u \u00ce S or v \u00ce S or both.<\/p>\r\n\"\"\r\n\r\n \r\n

      \r\n\r\nSolution<\/strong>\r\n\r\n \r\n\r\nLike vertex cover, set cover finds the minimum number of sets that covers all the elements.\r\n\r\n \r\n\r\nSome of the possible solutions are T = {s1, s3, s4} and T = {s1, s2}.\r\n\r\n \r\n

      Set cover is a NP hard problem as the solution involves guessing a subset of vertices, count them, and show that universal set is well covered. This is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible set covers becomes larger. Therefore, the algorithm for set cover becomes exponential algorithm. Therefore, set cover problem is NP hard.<\/p>\r\n \r\n\r\n(iii) Sum of Subsets<\/strong>\r\n\r\n \r\n\r\nGiven a <\/strong>set of positive numbers A = { a1, a2, \u2026, an } and constant C, find the set of elements whose sum equals C.\r\n\r\n \r\n\r\nExample 3:<\/strong>\u00a0\u00a0\u00a0\u00a0 Consider the following set, A = {7, 5, 19, 1, 12, 8, 14} and C = 21, Find one\r\n\r\n \r\n\r\nsolution.\r\n\r\n \r\n\r\nSolution<\/strong>\r\n\r\n \r\n\r\nOne solution is A\u00a2 = {7, 14} for C = 21. Some other solutions are {12,8,1}, {7,5,8,1}.\r\n\r\n \r\n\r\nIf C = 11, then there would be no solution at all.\r\n\r\n \r\n

      Sum of subsets is a NP hard problem. The solution of sum of subsets involves generating a a subset of numbers. If the sum of elements equals C, then the subset is a solution. Finding a solution is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible subsets becomes larger and algorithm becomes exponential as there are n! possible subsets for a set of \u2018n\u2019 elements. Therefore, the algorithm for sum of subsets becomes exponential algorithm. Therefore, sum of subsets is NP hard.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n(iv) Hamiltonian Cycle<\/strong>\r\n\r\n \r\n

      A Hamiltonian cycle is a closed path along n edges of G which visits every vertex once and returns to its starting vertex.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

      \r\n\r\nHamiltonian cycle is NP hard problem as there are are n<\/em>! different sequences of vertices that might <\/em>be Hamiltonian paths in a given n<\/em>-vertex graph [2,3].Therefore, if the number of vertices of graphs become larger, the algorithm becomes exponential. Therefore, Hamiltonian cycle problem is NP hard.\r\n\r\n \r\n\r\n \r\n\r\nSolution<\/strong>\r\n\r\n \r\n\r\nOne possible Hamiltonian cycle is given as 4, 3, 1, 2, 4.\r\n\r\n \r\n\r\nThe concept of NP \u2013 Completeness and proofs of some of these problems are NP-Complete is discussed in next module.\r\n\r\n \r\n\r\n \r\n\r\nSummary<\/strong>\r\n\r\n<\/div>\r\n\u00a0<\/strong>\r\n\r\nOne can conclude from this module 33 that\r\n
        \r\n \t
      • P and NP problems are important<\/li>\r\n \t
      • NP-Complete problems are problem whose status is unconfirmed.<\/li>\r\n \t
      • Non-Deterministic algorithms have important components \u2013 Guess and verification stage.<\/li>\r\n \t
      • Satisfiability problem is NP-Complete<\/li>\r\n<\/ul>\r\n \r\n\r\nReferences:<\/strong>\r\n\r\n \r\n
          \r\n \t
        1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\r\n \t
        2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t
        3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MI T Press, Cambridge, MA 1992.<\/li>\r\n \t
        4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.<\/li>\r\n<\/ol>\r\n \r\n\r\n ","rendered":"
          \n

          This module 33 focuses on NP-Complete problems. The module also discusses about Class P and NP problems. This module also introduces the theory of NP-Complete problems. The objectives of this module are<\/p>\n

           <\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the P and NP Class<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To understand NP-Complete problems<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To know some NP-Complete problems<\/p>\n

           <\/p>\n

          Computational Complexity<\/strong><\/p>\n

           <\/p>\n

          There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to problems called computational complexity theory [2,3].<\/p>\n

           <\/p>\n

          Algorithmic complexity theory [3,4] aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number<\/strong> n<\/em> is defined to be the number of binary bits needed to write n. For example,<\/em> Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.<\/p>\n

           <\/p>\n

          Asymptotic Analysis <\/strong>[1,2] refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.<\/p>\n

           <\/p>\n

          Computational complexity theory is different. Computational complexity aims to determine lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm.\u00a0In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds <\/span>defines the limits of the algorithm. Upper bound indicates the worst case performance of the algorithm and lower bound indicates the best case performance of the given algorithm.<\/span><\/p>\n<\/div>\n

          \n

           <\/p>\n

          Solvability of Problems<\/strong><\/p>\n

           <\/p>\n

          A problem is solvable<\/em> if there exists a program that always terminate and gives the answer.<\/p>\n

           <\/p>\n

          Solvability of the problems is related to the tractability of the problem [2,3].<\/p>\n

           <\/p>\n

          A problem is tractable<\/em> if it is solvable and we can say Time(x)\u2264(some polynomial).<\/em> The problems that can be solved using run time less than polynomial is called polynomial time algorithms.<\/p>\n

           <\/p>\n

          Class P Proble ms<\/strong><\/p>\n

           <\/p>\n

          P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. A problem is feasible if it has a solution cost as a polynomial. All problems that can be solved in polynomial time is called polynomial time or class P problems. Some of the examples of Class P problems are<\/p>\n

           <\/p>\n

           <\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Searching<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Element uniqueness<\/p>\n

          \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 graph connectivity<\/p>\n

           <\/p>\n

          Polynomial time algorithms also give a notion of efficient algorithms. All polynomial time algorithms are efficient algorithms as the problem can be solved. How about O(n log n)? or O(n2) ? yes. These algorithms are polynomial algorithms and hence solvable. On the other hand, the algorithms having complexity like O(2n) or O(n!) are not polynomial algorithms and instead are called exponential algorithms as these functions are not polynomial and whose growth is exponential and hence cannot be solved for larger instances.<\/p>\n<\/div>\n

          \n

           <\/p>\n

          What is NP Class?<\/strong><\/p>\n

           <\/p>\n

          The class of decision problems that can be solved by a non-deterministic polynomial algorithm is called class NP problem.<\/p>\n

           <\/p>\n

          What is a Non-deterministic algorithm? Non-deterministic algorithms produce an answer by a sequence \u201cGuesses\u201d while deterministic algorithms (like those that a computer executes) make decisions based on information.<\/p>\n

           <\/p>\n

           <\/p>\n

          Some of the examples of NP problems are given as follows:<\/p>\n

            \n
          • \u00a0 Traveling Salesman<\/li>\n
          • \u00a0 \u00a0N-Queens<\/li>\n
          • \u00a0 Classroom Scheduling<\/li>\n
          • \u00a0 \u00a0Packing<\/li>\n
          • \u00a0 \u00a0Scheduling<\/li>\n<\/ul>\n

             <\/p>\n

            These problems are hard problems as it is difficult to solve these problems for larger instances. Also, for most of these problems, no polynomial time algorithm is known and also it can be observed that most of these problems are combinatorial optimization problems. Most of the combinatorial problems are hard.<\/p>\n

             <\/p>\n

            What is a decision Problem?<\/p>\n

             <\/p>\n

            A decision problem is a problem whose output is a single Boolean value: YES or NO and NP is\u00a0 the set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.<\/p>\n<\/div>\n

            \n

             <\/p>\n

            One can conclude that from this discussion that some problems are hard to solve with the following characteristics:<\/p>\n

            l\u00a0\u00a0 No polynomial time algorithm is known<\/p>\n

            l\u00a0\u00a0 If answer is YES, then it can be checked in polynomial time<\/p>\n

            l\u00a0\u00a0 Most combinatorial optimization problems are hard<\/p>\n

             <\/p>\n

            Computational complexity is an exciting branch of algorithm analysis that discuss about these issues. The next module discusses about one important class of problems called NP-Complete problems.<\/p>\n

             <\/p>\n

             <\/p>\n

            Co-NP Proble ms<\/strong><\/p>\n

             <\/p>\n

            Co-NP is the opposite of NP. If the answer to a problem in co-NP is NO, then there is a proof of this fact in polynomial time [3].<\/p>\n

             <\/p>\n

            NP-I Proble ms<\/strong><\/p>\n

             <\/p>\n

            NP-I is called NP- Intermediate problems that are said to be between P and NP. Examples of NP-I problems are factoring problem and graph isomorphism problem.<\/p>\n

             <\/p>\n

            What is NP-Hard proble m?<\/strong><\/p>\n

             <\/p>\n

            NP-Hard are problems that are at least as hard as the hardest problems in NP. A problem A is NP-hard, if there is a polynomial algorithm exists, It implies polynomial algorithms for every problem in NP. In that case , P = NP whose proof is difficult. Clay Institute announced one million dollar prize in its web site for anyone who gives a proof. It is shown below with the other kinds of problems that are considered difficult (http:\/\/www.claymath.org\/millennium\/)<\/p>\n

             <\/p>\n

            1.\u00a0\u00a0\u00a0\u00a0\u00a0 Birch and Swinnerton-Dyer Conjecture<\/p>\n

            2.\u00a0\u00a0\u00a0\u00a0\u00a0 Hodge Conjecture<\/p>\n

            3.\u00a0\u00a0\u00a0\u00a0\u00a0 Navier-Stokes Equations<\/p>\n

            4.\u00a0\u00a0\u00a0\u00a0\u00a0 P vs NP<\/p>\n

            5.\u00a0\u00a0\u00a0\u00a0\u00a0 Poincar\u00e9 Conjecture<\/p>\n

            6.\u00a0\u00a0\u00a0\u00a0\u00a0 Riemann Hypothesis<\/p>\n<\/div>\n

            \n

            7.\u00a0\u00a0\u00a0 Yang-Mills Theory<\/p>\n

             <\/p>\n

             <\/p>\n

            NP-Complete Problems<\/strong><\/p>\n

             <\/p>\n

            NP-Complete (or NPC) problems are a set of problems that are well connected. A problem x that is in NP, if any one finds an polynomial time algorithm even for one problem, it implies that polynomial time algorithm for all NP-Complete problems. In other words: Problem x is in NP, then every problem in NP is reducible to problem x. Let us present the overview of NP-Complete Problems<\/p>\n

             <\/p>\n

            1. Decision Problems<\/strong><\/p>\n

             <\/p>\n

            A decision problem is a problem whose output is a single Boolean value: YES or NO . NP is the\u00a0 set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.<\/p>\n

             <\/p>\n

            2. Language Frame work<\/strong><\/p>\n

             <\/p>\n

            Let us review some of the important jargons based on [3]\u00a0 now.<\/p>\n

             <\/p>\n

            Alphabet: An alphabet is a finite set of symbols. For example A = {0,1}<\/p>\n

             <\/p>\n

            String: A finite sequence of symbols<\/p>\n

             <\/p>\n

            Empty String: A string of zero length<\/p>\n

             <\/p>\n

            Language: A set of strings is called a Language<\/p>\n

             <\/p>\n

            Complementary Language: if the strings are not in L, then it is called complementary Language.<\/p>\n

             <\/p>\n

            3. Proble m Encoding<\/strong><\/p>\n

             <\/p>\n

            Then the decision problem is encoded using Turing machine. Turing machine takes the encoding of the given problem and performs the following actions.<\/p>\n

             <\/p>\n

            \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If input string is invalid, then Reject<\/p>\n

            \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If input string is valid, but output No, then reject<\/p>\n

            \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 If String is valid and output is Yes, then Accept.<\/p>\n

             <\/p>\n

            One can summarize this for language L as follows:<\/p>\n

             <\/p>\n

            P = { L | L is accepted by a deterministic Turing Machine in polynomial time }<\/p>\n<\/div>\n

            \n

            NP = { L | L is accepted by a non-deterministic Turing Machine in polynomial time }<\/p>\n

             <\/p>\n

            NP-Complete problem can be formally defined as follows:<\/p>\n

             <\/p>\n

            Q\u00a0 is an NP-Complete problem iff<\/p>\n

             <\/p>\n

            1) Q is in NP<\/p>\n

             <\/p>\n

            2) every other NP problem polynomial time reducible to Q<\/p>\n

             <\/p>\n

            So, to prove a problem A is NP-Complete, then reduce a known NP-C problem to A. Hence, reductions are basis of NP-Complete problems.<\/p>\n

             <\/p>\n

            NP-Complete problems are solved by non-deterministic algorithms. A non-deterministic algorithm consists of two phases. The first phase is guessing of solutions and the second phase is the verification of the guesses using an algorithm or certificate. If the verification stage of a nondeterministic algorithm is of polynomial time-complexity, then this algorithm is called an NP (nondeterministic polynomial) algorithm [1,2,3].<\/p>\n

             <\/p>\n

            The verification algorithm A has two components. One is input string x and another string called certificate. Certificate is another string y. It takes the input string x, and if A(x,y) = 1 implies the language is verified by the verification algorithm<\/p>\n

             <\/p>\n

            One of the famous NP-Complete problems is Circuit Satisfiability problem. It can be formalized as follows: Given a Boolean circuit, consisting of gates such as, NOT, OR, AND, Is there any set of inputs that makes the circuit output TRUE. Simultaneously, one can check for circuit output NO also.<\/p>\n

             <\/p>\n

             <\/p>\n

            Cook-Levin theore m states that: Circuit- SAT is NP-Complete. [3]<\/strong><\/p>\n

             <\/p>\n

             <\/p>\n

            The circuit Satisfiability is formulated mathematically as follows: Given a Boolean formula, determine whether this formula is satisfiable or not.<\/p>\n

             <\/p>\n

            A\u00a0 literal : xi or -xi<\/p>\n<\/div>\n

            A clause : x1 v x2 v – x3 \u00ba Ci<\/p>\n

             <\/p>\n

            A formula : conjunctive normal form<\/p>\n

             <\/p>\n

            C1& C2 & \u2026 & Cm<\/p>\n

             <\/p>\n

             <\/p>\n

            Example 1: <\/strong>Is there any one assignment that makes the expression true :<\/p>\n

             <\/p>\n

            x1 v x2 v x3<\/p>\n

              \n
            • & – x1<\/li>\n
            • & – x2<\/li>\n<\/ul>\n

              Solution:<\/p>\n

               <\/p>\n

              It can be observed that the following assignment x1 \u2190 F , x2 \u2190 F , x3 \u2190 T will make the above formula true<\/p>\n

               <\/p>\n

              A related problem is called Formula Satisfiability problem. A Boolean formula is in CNF (Conjunctive Normal Form) if it is a conjunction (AND) of clauses. All clauses are disjunction (OR) of many literals. Every literal is a variable or its negation.<\/p>\n

               <\/p>\n

              Another related problem is 3-SAT. In 3-SAT or 3SAT, there must be exactly 3 literals per clause. 3-SAT problem is : Given 3-CNF formula, Is there an assignment that makes the formula to evaluate to TRUE.<\/p>\n

               <\/p>\n

               <\/p>\n

              Examples of NP Hard Proble ms<\/strong><\/p>\n

               <\/p>\n

               <\/p>\n

              Some of the known NP Hard problems are listed here. One of the major NP hard problem is vertex cover.<\/p>\n

               <\/p>\n

              (i) Vertex Cover<\/p>\n

               <\/p>\n

              Vertex cover is an important problem. It is formally stated as follows: Given a graph G=(V, E), S is the node cover if S \u00cd V and for every edge (u, v) \u00ce E, either u \u00ce S or v \u00ce S or both.<\/p>\n

              \"\"<\/p>\n

               <\/p>\n

              \n

              Solution<\/strong><\/p>\n

               <\/p>\n

              Like vertex cover, set cover finds the minimum number of sets that covers all the elements.<\/p>\n

               <\/p>\n

              Some of the possible solutions are T = {s1, s3, s4} and T = {s1, s2}.<\/p>\n

               <\/p>\n

              Set cover is a NP hard problem as the solution involves guessing a subset of vertices, count them, and show that universal set is well covered. This is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible set covers becomes larger. Therefore, the algorithm for set cover becomes exponential algorithm. Therefore, set cover problem is NP hard.<\/p>\n

               <\/p>\n

              (iii) Sum of Subsets<\/strong><\/p>\n

               <\/p>\n

              Given a <\/strong>set of positive numbers A = { a1, a2, \u2026, an } and constant C, find the set of elements whose sum equals C.<\/p>\n

               <\/p>\n

              Example 3:<\/strong>\u00a0\u00a0\u00a0\u00a0 Consider the following set, A = {7, 5, 19, 1, 12, 8, 14} and C = 21, Find one<\/p>\n

               <\/p>\n

              solution.<\/p>\n

               <\/p>\n

              Solution<\/strong><\/p>\n

               <\/p>\n

              One solution is A\u00a2 = {7, 14} for C = 21. Some other solutions are {12,8,1}, {7,5,8,1}.<\/p>\n

               <\/p>\n

              If C = 11, then there would be no solution at all.<\/p>\n

               <\/p>\n

              Sum of subsets is a NP hard problem. The solution of sum of subsets involves generating a a subset of numbers. If the sum of elements equals C, then the subset is a solution. Finding a solution is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible subsets becomes larger and algorithm becomes exponential as there are n! possible subsets for a set of \u2018n\u2019 elements. Therefore, the algorithm for sum of subsets becomes exponential algorithm. Therefore, sum of subsets is NP hard.<\/p>\n<\/div>\n

               <\/p>\n

              (iv) Hamiltonian Cycle<\/strong><\/p>\n

               <\/p>\n

              A Hamiltonian cycle is a closed path along n edges of G which visits every vertex once and returns to its starting vertex.<\/p>\n

               <\/p>\n

              \"\"<\/p>\n

               <\/p>\n

              \n

              Hamiltonian cycle is NP hard problem as there are are n<\/em>! different sequences of vertices that might <\/em>be Hamiltonian paths in a given n<\/em>-vertex graph [2,3].Therefore, if the number of vertices of graphs become larger, the algorithm becomes exponential. Therefore, Hamiltonian cycle problem is NP hard.<\/p>\n

               <\/p>\n

               <\/p>\n

              Solution<\/strong><\/p>\n

               <\/p>\n

              One possible Hamiltonian cycle is given as 4, 3, 1, 2, 4.<\/p>\n

               <\/p>\n

              The concept of NP \u2013 Completeness and proofs of some of these problems are NP-Complete is discussed in next module.<\/p>\n

               <\/p>\n

               <\/p>\n

              Summary<\/strong><\/p>\n<\/div>\n

              \u00a0<\/strong><\/p>\n

              One can conclude from this module 33 that<\/p>\n

                \n
              • P and NP problems are important<\/li>\n
              • NP-Complete problems are problem whose status is unconfirmed.<\/li>\n
              • Non-Deterministic algorithms have important components \u2013 Guess and verification stage.<\/li>\n
              • Satisfiability problem is NP-Complete<\/li>\n<\/ul>\n

                 <\/p>\n

                References:<\/strong><\/p>\n

                 <\/p>\n

                  \n
                1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/li>\n
                2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n
                3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MI T Press, Cambridge, MA 1992.<\/li>\n
                4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.<\/li>\n<\/ol>\n

                   <\/p>\n

                   <\/p>\n","protected":false},"author":4,"menu_order":12,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-142","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":3,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/142\/revisions"}],"predecessor-version":[{"id":147,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/142\/revisions\/147"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/142\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=142"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=142"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=142"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}