Analyzing Algorithms and Problems

Analyzing Algorithms and Problems

RAIK 283 Data Structures & Algorithms P, NP, and NP-Complete Dr. Ying Lu [email protected] 1 RAIK 283 Data Structures & Algorithms Giving credit where credit is due: Most of the lecture notes are based on slides created by Dr. Cusack and Dr. Leubke. I have modified them and added new slides

2 Tractability Some problems are intractable: as they grow large, we are unable to solve them in reasonable time What constitutes reasonable time? Standard working definition: polynomial time On an input of size n the worst-case running time is O(nk) for some constant k O(n2), O(n3), O(1), O(n lg n), O(2n), O(nn), O(n!) Polynomial time: O(n2), O(n3), O(1), O(n lg n)

Not in polynomial time: O(2n), O(nn), O(n!) 3 Polynomial-Time Algorithms Are some problems solvable in polynomial time? Of course: many algorithms weve studied provide polynomial-time solutions to some problems Are all problems solvable in polynomial time? No: Turings Halting Problem is not solvable by any computer, no matter how much time is given

Most problems that do not yield polynomial-time algorithms are either optimization or decision problems. 4 Optimization/Decision Problems Optimization Problems An optimization problem is one which asks, What is the optimal solution to problem X? Examples:

0-1 Knapsack Fractional Knapsack Minimum Spanning Tree Decision Problems An decision problem is one with yes/no answer Examples: Does a graph G have a MST of weight W? 5

Optimization/Decision Problems An optimization problem tries to find an optimal solution A decision problem tries to answer a yes/no question Many problems will have decision and optimization versions Eg: Traveling salesman problem optimization: find hamiltonian cycle of minimum weight decision: is there a hamiltonian cycle of weight k

Some problems are decidable, but intractable: as they grow large, we are unable to solve them in reasonable time Is there a polynomial-time algorithm that solves the problem? 6 The Class P P: the class of decision problems that have polynomial-time deterministic algorithms. That is, they are solvable in O(p(n)), where p(n) is a polynomial on n A deterministic algorithm is (essentially) one that always computes the correct answer Why polynomial? if not, very inefficient nice closure properties

the sum and composition of two polynomials are always polynomials too 7 Sample Problems in P Fractional Knapsack MST Sorting Others?

8 The class NP NP: the class of decision problems that are solvable in polynomial time on a nondeterministic machine (or with a nondeterministic algorithm) (A determinstic computer is what we know) A nondeterministic computer is one that can guess the right answer or solution Think of a nondeterministic computer as a parallel machine that can freely spawn an infinite number of processes Thus NP can also be thought of as the class of problems whose solutions can be verified in polynomial time

Note that NP stands for Nondeterministic Polynomial-time 9 Sample Problems in NP Fractional Knapsack MST Sorting Others? Hamiltonian Cycle (Traveling Salesman) Graph Coloring

Satisfiability (SAT) the problem of deciding whether a given Boolean formula is satisfiable 10 The Satisfiability (SAT) Problem Satisfiability (SAT): Given a Boolean expression on n variables, can we assign values such that the expression is TRUE? Ex: ((x1 x2) ((x1 x3) x4)) x2 Seems simple enough, but no known deterministic

polynomial time algorithm exists Easy to verify in polynomial time! 11 Example: CNF satisfiability This problem is in NP. Nondeterministic algorithm: Guess truth assignment Check assignment to see if it satisfies CNF formula

Example: (AB C ) (A B) ( B D F ) (F D) Truth assignments: ABCDEF 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 ... (how many more?)

Checking phase: (n) 12 Review: P And NP Summary P = set of problems that can be solved in polynomial time Examples: Fractional Knapsack, NP = set of problems for which a solution can be verified in polynomial time Examples: Fractional Knapsack,, Hamiltonian Cycle, CNF SAT, 3-CNF SAT

Clearly P NP Open question: Does P = NP? Most suspect not An August 2010 claim of proof that P NP, by Vinay Deolalikar, researcher at HP Labs, Palo Alto, has flaws 13 NP-complete problems A decision problem D is NP-complete iff 1. D NP 2. every problem in NP is polynomial-time reducible to D

Cooks theorem (1971): CNF-sat is NP-complete 14 Reduction A problem R can be reduced to another problem Q if any instance of R can be rephrased to an instance of Q, the solution to which provides a solution to the instance of R This rephrasing is called a transformation

Intuitively: If R reduces in polynomial time to Q, R is no harder to solve than Q Example: lcm(m, n) = m * n / gcd(m, n), lcm(m,n) problem is reduced to gcd(m, n) problem 15 NP-Hard and NP-Complete If R is polynomial-time reducible to Q, we denote this R p Q

Definition of NP-Hard and NP-Complete: If all problems R NP are polynomial-time reducible to Q, then Q is NP-Hard We say Q is NP-Complete if Q is NP-Hard and Q NP If R p Q and R is NP-Hard, Q is also NP-Hard (why?) 16 Practical Implication Given a problem that is known to be NP-Complete

Try to solve it by designing a polynomial-time algorithm? Prove P=NP Alleviate the intractability of such problems To make some large instances of the problem solvable (like solving some instances of Knapsack problem in polynomial time) To find good approximations (Chap 12) 17 Appendix

The following slides are from a document by Dr. Robins, University of Virginia 18 19 20

Recently Viewed Presentations

  • Tax-Time Saver Story - Federal Reserve Bank of Dallas

    Tax-Time Saver Story - Federal Reserve Bank of Dallas

    Expanding the Savings Agenda RAISE Texas SummitFederal Reserve Bank of Dallas—Houston BranchOctober 30, 2012 Laura RosenOpportunityTexas. How the RAISE Texas network is helping to build a savings movement in Texas, focusing on growth in tax-time and college and children's savings.
  • Spotswood High School - Osbourn Park High School

    Spotswood High School - Osbourn Park High School

    Introduction to Naviance. Naviance can help you decide your education/career path. Naviance is a web-based resource for students and parents that encourages and supports post high school career and college planning. Family Connection is specific to our school. Family Connection...
  • Initiatives in 100 GE for Fermilab R&D Large

    Initiatives in 100 GE for Fermilab R&D Large

    End-to-end experiment analysis systems include a deep stack of software layers and services. ... 2011: ANI Long Island MAN (LIMAN) testbed. Tested GridFTP and Globus Online for the data movement use cases of HEP over 3x10GE. 2011-2012: Super Computing 2011....
  • The Macroscopic behavior of the TCP Congestion Avoidance ...

    The Macroscopic behavior of the TCP Congestion Avoidance ...

    The Macroscopic behavior of the TCP Congestion Avoidance Algorithm Introduction: Analysis of a performance model for the TCP Congestion Avoidance Algorithm Verification of the model through both simulation and live Internet measurements Assumptions: TCP Congestion Avoidance Algorithm in steady-state Light...
  • INTOSAI-Donor Cooperation

    INTOSAI-Donor Cooperation

    From theGlobal SAI Stocktaking Report 2014: "when comparing the extent of support to the INTOSAI region's country distribution and its overall SAI results, it becomes clear that the distribution of funds from donors, are not corresponding with the level of...
  • From Cesium to X-Ray:A Cell Therapy Perspective

    From Cesium to X-Ray:A Cell Therapy Perspective

    Cell Characteristics. Viable cell numbers declined in both irradiated conditions. There was no statistically significant difference in the viability between X-Ray and Gamma radiation for all time points (p=0.73, two-tailed t-test).
  • Data Privacy - The Problem

    Data Privacy - The Problem

    Or Sheffet, Athabasca 3-04. Office hours 15:30-16:00 Tuesdays / coordinate via email. [email protected] (subject must begin with [CMPUT651]) Abysmal handwriting. Mumbler. Not a native English-speaker. Not native to Canada. ASK QUESTIONS!
  • PowerPoint-presentatie

    PowerPoint-presentatie

    Onteigeningen op rooilijnen en leegstand ten gevolge van onverdeeldheid moeten juridisch worden gedeblokkeerd. 20. Het lokaal bestuur is het best geplaatst om noden aan te voelen, de regie van het lokale woonbeleid op zich te nemen en pistes voor nieuwe...