Polynomial Time Reduction

Return to List of Lectures

Previous Lecture

• Misc
  • Research weekend colloquium
    • “Quantum Game Theory”
    • Prof. Tom Cooney
    • Friday, November 13, 4:00 PM
    • Newton 203
    • Usual extra credit offer
• Optional Presentations
  • Handout available online, will be on paper Tuesday
• Questions?
• Reductions and NP Completeness
  • Summary of section 34.3 through “Reducibility”
    • Notation {0,1}* ?
      • = set of all strings formable using 0, 1
        • e.g., 001101, 0, 1, ε (aka empty string)
      • * = Kleene closure: S* = set of strings formable by 0 or more concatenations of strings from S
        • { cat, dog }* = { ε , cat, dog, catdog, catcatdog, … }
    • Reduction = mapping between languages L₁ and L₂ in order to use decider for L₂ to decide L₁
    • Polynomial time reduction means mapping can be computed in Θ(n^k) time where n is length of string and k is constant
  • Reduction examples
    • Dot product ≤_p matrix multiplication (a fairly informal but intuitive example)
      • Idea: Dot product is just simple form of matrix multiplication
      • Dot product: input vectors v₁ and v₂ both of length n
      • Matrix multiplication: input matrices M₁ (n by m) and M₂ (m by k)
      • Reduction:
        • Create M₁ = v₁
        • Create M₂ = v₂^T
      • Runs in time Θ(n) by copying elements
    • Transitive closure ≤_p PATH (more typical of formal reductions in complexity theory)
      • Transitive closure of a relation R = R* such that (a,b) in R* iff (a,c₁), (c₁,c₂), …, (c_n, b) all in R
      • Define transitive closure problem to take a relation R and a pair (a,b) as inputs, and to accept iff (a,b) in R*.
      • PATH( G, u, v, k ): accept if graph G has a path from vertex u to vertex v of length at most k edges
      • Reduction:
        • Given R of n pairs and (x,y)
        • Create graph G:
          • For each pair (a,b) in R
            • Add directed edge (a,b) to G
              
      • Time looks like Θ(n)
    • Sorting with runs
      • Run = contiguous subsequence of A that is in sorted order, i.e., A_i ≤ A_i+1 ≤ … ≤ A_j
      • Define sorting-with-runs to be sorting except input is divided into runs of length ≥ 1 by markers “*”
        • e.g., 3, 7, *, 5, *, 2, 9, 10, * 6, 8
      • Show that sorting ≤_p sorting-with-runs
        • Reduction:
          • Given list L of n items to sort
          • Create list L′ = L₁, *, L₂, *, …, *, L_n
        • Takes time Θ(n)
      • What is a lower bound for sorting-with-runs?
        • Ω( n logn ) because anything less would imply a less-than-Θ( n logn ) time algorithm for sorting, which we know is impossible
  • NP complete problem = problem that everything in NP reduces to in polynomial time
• Next
  • NP completeness of circuit satisfiability
  • Read section 34.3 from “NP-completeness” through end
    • Bottom of page 1068 through top of 1077

Next Lecture