Challenging Problems in Computation Theory

np np complete complete prof manjusha amritkar n.w
1 / 21
Embed
Share

Exploring complex problems like the Traveling Salesman, Bin Packing, Hall Room Allocation, and Discovery vs. Verification in the context of solution discovery versus solution verification in computational theory at the Hope Foundation's International Institute of Information Technology, Pune.

  • Computation Theory
  • Challenging Problems
  • Solution Discovery
  • Solution Verification
  • Hope Foundation

Uploaded on | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


  1. NP NP- -COMPLETE COMPLETE Prof. Manjusha Amritkar Assistant Professor Department of Information Technology Hope Foundation s International Institute of Information Technology, I IT www.isquareit.edu.in

  2. T THE HE T TRAVELING RAVELING S SALESMAN ALESMAN P PROBLEM ROBLEM Suppose that you are given the road map of India. You need to find a traversal that covers all the cities/towns/villages of population 1, 000. And the traversal should have a short distance, say, 9, 000 kms. You will have to generate a very large number of traversals to find out a short traversal. Suppose that you are also given a claimed short traversal. It is now easy to verify that given claimed traversal is indeed a short traversal. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  3. T THE HE B BIN IN P PACKING ACKING P PROBLEM ROBLEM Suppose you have a large container of volume 1000 cubic meter and 150 boxes of varying sizes with volumes between 10 to 25 cubic meters. You need to fit at least half of these boxes in the container. You will need to try out various combinations of 75 boxes (there are 1040 combinations) and various ways of laying them in the container to find a fitting. Suppose that you are also given a set of 75 boxes and a way of laying them. It is now easy to verify if these 75 boxes layed out in the given way will fit in the container. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  4. H HALL ALL- -I R I ROOM OOM A ALLOCATION LLOCATION Each wing of Hall-I has 72 rooms. Suppose from a batch of 540 students, 72 need to be housed in C-wing. There are several students that are incompatible with each other, and so no such pair should be present in the wing. If there are a large number of incompatibilities, you will need to try out many combinations to get a correct one. Suppose you are also given the names of 72 students to be housed. It is now easy to verify if they are all compatible. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  5. D DISCOVERY ISCOVERYVERSUS VERSUS V VERIFICATION ERIFICATION In all these problems, finding a solution appears to be far more difficult than checking the correctness of a given solution. Informally, this makes sense as discovering a solution is often much more difficult than verifying its correctness. Can we formally prove this? Leads to the P versus NP problem. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  6. F FORMALIZING ORMALIZING E EASY ASY- -TO TO- -SOLVE SOLVE A problem is easy to solve if the solution can be computed quickly. Gives rise to two questions: I. How is it computed? II. How do we define quickly ? Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  7. C COMPUTING OMPUTING M METHOD ETHOD We will use an algorithm to compute. In practice, the algorithm will run on a computer via a computer program. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  8. A ALGORITHMS LGORITHMS An algorithm is a set of precise instructions for computation. The algorithm can perform usual computational steps, e.g., assignments, arithmetic and Boolean operations, loops. For us, an algorithm will always have input presented as a sequence of bits. The input size is the number of bits in the input to the algorithm. The algorithm stops after outputting the solution. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  9. T TIME IME C COMPLEXITY OMPLEXITYOF OF P PROBLEMS ROBLEMS A problem has time complexity TA(n) if there is an algorithm A that solves the problem on every input. Addition has time complexity O(n). Multiplication has time complexity O(n2) Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  10. T TIME IME M MEASUREMENT EASUREMENT Let A be an algorithm and x be an input to it. Let TA(x) denote the number of steps of the algorithm on input x. Let TA(n) denote the maximum of TA(x) over all inputs x of size n. We will use TA(n) to quantify the time taken by algorithm A to solve a problem on different input sizes. For example, an algorithm A that adds two n bit numbers using school method has TA(n) = O(n). An algorithm B that multiplies two n bits numbers using school method has TA(n) = O(n2) Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  11. Q QUANTIFYING UANTIFYING E EASY ASY- -TO TO- -COMPUTE COMPUTE The problems of adding and multiplying are definitely easy. Also, if a problem is easy, and another problem can be solved in time n T(n) where T(n) is the time complexity of the easy problem, then the new problem is also easy. This leads to the following definition: A problem is efficiently solvable if its time complexity is n O(1) . Such problems are also called polynomial- time problems. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  12. T THE HE C CLASS LASS P P The class P contains all efficiently solvable problems. Specifically, they are the problems that can be solved in time O(n k) for some constant k, where n is the size of input to the problem. Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  13. T THE HE C CLASS LASS NP NP NP = Non-Deterministic polynomial time The class NP contains those problems that are verifiable in polynomial time. e.g 1. Hamiltonian cycle Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  14. H HAMILTONIAN AMILTONIAN C CYCLE YCLE Determining whether a directed graph has a Hamiltonian cycle does not have a polynomial time algorithm (yet!) However if someone was to give you a sequence of vertices, determining whether or not that sequence forms a Hamiltonian cycle can be done in polynomial time Therefore Hamiltonian cycles are in NP Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  15. SAT A boolean formula is satisfiable if there exists some assignment of the values 0 and 1 to its variables that causes it to evaluate to 1. CNF Conjunctive Normal Form. ANDing of clauses of ORs Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  16. 2-CNF SAT Each or operation has two arguments that are either variables or negation of variables The problem in 2 CNF SAT is to find true/false(0 or 1) assignments to the variables in order to make the entire formula true. Any of the OR clauses can be converted to implication clauses ( x y) ( y z) (x z) (z y) Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  17. 2-SAT ISIN P Create the implication graph x y x y z z Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  18. SATISFIABILITYVIAPATHFINDING If there is a path from And if there is a path from Then FAIL! How to find paths in graphs? DFS/BFS and modifications thereof Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  19. 3 CNF SAT (3 SAT) Not so easy anymore. Implication graph cannot be constructed No known polytime algorithm Is it NP? If someone gives you a solution how long does it take to verify it? Make one pass through the formula and check This is an NP problem Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in

  20. REFERENCES Contents are referred from following web resources https://www.seas.upenn.edu/~bhusnur4/cit596_sp ring2014/PNP.pptx https://www.cse.iitk.ac.in/users/manindra/present ations/IITKTalk.pdf

  21. THANK YOU For further details, please contact Manjusha Amritkar manjushaa@isquareit.edu.in Department of Information Technology Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 www.isquareit.edu.in | info@isquareit.edu.in

Related


More Related Content