8 PPT Complexity Classes P, NP, NP-hard and NP-complete.pptx

8 PPT Complexity Classes P, NP, NP-hard and NP-complete

1. Complexity Classes

2. P versus NP Problem   The   P versus NP problem   is a major   unsolved problem in computer science . It asks whether every problem whose solution can be quickly verified can also be solved quickly.     It is one of the seven   Millennium Prize Problems   selected by the   Clay Mathematics Institute , each of which carries a US$1,000,000 prize for the first correct solution.

3. A  polynomial-time reduction  is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second. Polynomial-time Reduction Note: A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either.

4. Many-one Reductions A polynomial-time many-one reduction  from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem.  An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial-time many-one reductions may also be known as  polynomial transformations  or  Karp reductions , named after  Richard Karp .

5. Polynomial Reductions (Contd.) If problem X can be reduced to problem Y, we denote this by X ≤ P Y. This means X is polynomal -time reducible to Y . It also means that Y is at least as hard as X because if you can solve Y, you can solve X.

6.   The   Cook–Levin theorem , also known as  Cook's theorem , states that the Boolean satisfiability problem is NP-complete. Stephen Cook  published his paper "The complexity of theorem proving procedures" in conference proceedings of the ACM Symposium on Theory of Computing in 1971.    Richard Karp's subsequent paper in 1972 titled, "Reducibility among combinatorial problems", generated renewed interest in Cook's paper by providing a list of 21 NP-complete problems.   Cook and Karp received a Turing Award for this work.     Cook, Stephen  (1971).  " The complexity of theorem proving procedures " .  Proceedings of the Third Annual ACM Symposium on Theory of Computing . pp. 151–158.  doi : 10.1145/800157.805047 .     Karp, Richard M.  (1972).  " Reducibility Among Combinatorial Problems "  (PDF). In Raymond E. Miller; James W. Thatcher (eds.).  Complexity of Computer Computations . New York: Plenum. pp. 85–103.  ISBN   0-306-30707-3 . Cook`s Theorem

7. How to Prove that a Problem is NP-Complete? NP-Complete problems are the ones that are both in   NP and   NP -Hard . So, to prove that a problem is   NP-Complete we need to show that the problem: belongs to  NP is  NP -Hard   How to show that a problem is NP?     How to show that a problem is NP-Hard? To show that the problem is   NP-Hard, we have to choose another   NP-Hard problem and reduce the chosen problem to ours.

8. A vertex cover of a graph is a set S of vertices such that every edge has at least one endpoint in S . Vertex Cover: Definition

9. Thank You