Introduction to Computational Complexity Theory pptx

Tractable and Intractable Problems, The P and NP Classes, Polynomial Time Reductions, The NP- Hard and NP-Complete Classes
A problem that is solvable by a polynomial-time algorithm.�The upper bound is polynomial.�Here are examples of tractable problems (ones with known polynomial-time algorithms):�– Searching an unordered list�– Searching an ordered list�– Sorting a list�– Multiplication of integers �– Finding a minimum spanning tree in a graph
a problem that cannot be solved by a polynomial-time algorithm.
The lower bound is exponential.�From a computational complexity stance, intractable problems are problems for which there exist no efficient algorithms to solve them.�Most intractable problems have an algorithm that provides a solution, and that algorithm is the brute-force search.�This algorithm, however, does not provide an efficient solution and is, therefore, not feasible for computation with anything more than the smallest input.
Examples�Towers of Hanoi: we can prove that any algorithm that solves this problem must have a worst-case running time that is at least 2n − 1.�* List all permutations (all possible orderings) of n numbers.
In computer science, there exist some problems whose solutions are not yet found, the problems are divided into classes known as Complexity Classes.
These classes help scientists to group problems based on how much time and space they require to solve problems and verify the solutions.
Complexity classes are useful in organising similar types of problems.
P Class
NP Class
3. NP-hard
4. NP-complete
The class P stands for polynomial time. P class consists of problems that can be solved by a deterministic machine in polynomial time. , i.e. these problems can be solved in time O(n^k) in worst-case, where k is constant.
The solution to P problems is easy to find. 
These problems are called tractable, while others are called intractable or superpolynomial.
Formally, an algorithm is polynomial time algorithm, if there exists a polynomial time algorithm p(n) such that the algorithm can solve any instance of size n in a time O(p(n)).
Problem requiring Ω(n50) time to solve are essentially intractable for large n. Most known polynomial time algorithm run in time O(nk) for fairly low value of k.
The advantages in considering the class of polynomial-time algorithms is that all reasonable deterministic single processor model of computation.
The NP in NP class stands for Non-deterministic Polynomial Time.
It is the collection of decision problems that can be solved by a non-deterministic machine in polynomial time.
The solutions of the NP class are hard to find since they are being solved by a non-deterministic machine but the solutions are easy to verify.
 The class NP consists of those problems that are verifiable in polynomial time.
NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information.
Hence, we aren’t asking for a way to f

1. Unit 6 Introduction to Complexity Theory Tractable and Intractable Problems, The P and NP Classes, Polynomial Time Reductions, The NP- Hard and NP-Complete Classes

2. Tractable and Intractable Problems

3. Tractable and Intractable Problems

4. Tractable and Intractable Problems

5. Tractable Problem: A problem that is solvable by a polynomial-time algorithm. The upper bound is polynomial. Here are examples of tractable problems (ones with known polynomial-time algorithms): – Searching an unordered list – Searching an ordered list – Sorting a list – Multiplication of integers – Finding a minimum spanning tree in a graph

6. Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential. From a computational complexity stance, intractable problems are problems for which there exist no efficient algorithms to solve them. Most intractable problems have an algorithm that provides a solution, and that algorithm is the brute-force search. This algorithm, however, does not provide an efficient solution and is, therefore, not feasible for computation with anything more than the smallest input. Examples Towers of Hanoi: we can prove that any algorithm that solves this problem must have a worst-case running time that is at least 2 n − 1. * List all permutations (all possible orderings) of n numbers.

7. Complexity Classes: In computer science, there exist some problems whose solutions are not yet found, the problems are divided into classes known as  Complexity Classes . These classes help scientists to group problems based on how much time and space they require to solve problems and verify the solutions. Complexity classes are useful in organising similar types of problems. P Class NP Class 3. NP-hard 4. NP-complete

8. P-Class The class P stands for polynomial time. P class consists of problems that can be solved by a deterministic machine in polynomial time. , i.e. these problems can be solved in time O( n^k ) in worst-case, where k is constant . The solution to P problems is easy to find .  These problems are called tractable , while others are called intractable or superpolynomial . Formally, an algorithm is polynomial time algorithm, if there exists a polynomial time algorithm p(n) such that the algorithm can solve any instance of size n in a time O(p(n)) . Problem requiring Ω(n 50 ) time to solve are essentially intractable for large n . Most known polynomial time algorithm run in time O( n k ) for fairly low value of k . The advantages in considering the class of polynomial-time algorithms is that all reasonable deterministic single processor model of computation.

9. NP-Class The NP in NP class stands for Non-deterministic Polynomial Time. It is the collection of decision problems that can be solved by a non-deterministic machine in polynomial time. The solutions of the NP class are hard to find since they are being solved by a non-deterministic machine but the solutions are easy to verify.   The class NP consists of those problems that are verifiable in polynomial time. NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. Hence, we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct. Every problem in this class can be solved in exponential time using exhaustive search. Example: Hamiltonian Circuit Problem Graph Coloring Problem

10. P versus NP Every decision problem that is solvable by a deterministic polynomial time algorithm is also solvable by a polynomial time non-deterministic algorithm. All problems in P can be solved with polynomial time algorithms, whereas all problems in NP - P are intractable. It is not known whether P = NP . However, many problems are known in NP with the property that if they belong to P, then it can be proved that P = NP. If P ≠ NP , there are problems in NP that are neither in P nor in NP-Complete. The problem belongs to class P if it’s easy to find a solution for the problem. The problem belongs to NP , if it’s easy to check a solution that may have been very tedious to find.

11. What is Reduction?  Let  L1  and  L2  be two decision problems. Suppose algorithm  A2  solves  L2 . That is, if  y  is an input for  L2  then algorithm  A2  will answer Yes or No depending upon whether  y  belongs to  L2  or not. The idea is to find a transformation from  L1  to  L2  so that algorithm  A2  can be part of algorithm  A1  to solve  L1 .

12. Polynomial-Time Reduction In computational complexity theory , 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

13. 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. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems for those classes.

14. Types of reductions The three most common types of polynomial-time reduction, from the most to the least restrictive, are polynomial-time many-one reductions , truth-table reductions , and Turing reductions . The most frequently used of these are the many-one reductions, and in some cases the phrase "polynomial-time reduction" may be used to mean a polynomial-time many-one reduction. The most general reductions are the Turing reductions and the most restrictive are the many-one reductions with truth-table reductions occupying the space in between

15. Many-one reductions 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 .

16. Truth-table reductions A polynomial-time truth-table reduction from a problem A to a problem B (both decision problems) is a polynomial time algorithm for transforming inputs to problem A into a fixed number of inputs to problem B, such that the output for the original problem can be expressed as a function of the outputs for B. The function that maps outputs for B into the output for A must be the same for all inputs, so that it can be expressed by a truth table

17. . Turing reductions A polynomial-time Turing reduction from a problem A to a problem B is an algorithm that solves problem A using a polynomial number of calls to a subroutine for problem B , and polynomial time outside of those subroutine calls. Polynomial-time Turing reductions are also known as Cook reductions , named after Stephen Cook . Many-one reductions can be regarded as restricted variants of Turing reductions where the number of calls made to the subroutine for problem B is exactly one and the value returned by the reduction is the same value as the one returned by the subroutine.

18. NP-Hard Class An NP-hard problem is at least as hard as the hardest problem in NP and it is a class of problems such that every problem in NP reduces to NP-hard. Features: All NP-hard problems are not in NP. It takes a long time to check them. This means if a solution for an NP-hard problem is given then it takes a long time to check whether it is right or not. A problem A is in NP-hard if, for every problem L in NP, there exists a polynomial-time reduction from L to A.

19. NP-Complete Class A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP. Features: NP-complete problems are special as any problem in NP class can be transformed or reduced into NP-complete problems in polynomial time. If one could solve an NP-complete problem in polynomial time, then one could also solve any NP problem in polynomial time. Some example problems include: Hamiltonian Cycle. Satisfiability. Vertex cover .

20. Relation Between P, NP, NP Hard, Np Complete Classes

21. Thank You