Outline

• Last time...
  • IsSorted
    • Given an array, determine if its elements are in non-descending order:
  • Hamiltonian path
    • Given a graph and vertices s and t, determine if there is a path from s to t that visits every vertex exactly once.
  • SubsetSum
    • Given a list of integers and target sum, determine if a subset adds to the target.
  • Satisfiable
    • Given a boolean expression, determine if there is an assignment to variables that makes it true.
• How can we compare the difficulty of problems?
  • Example: Bipartite matching vs. Network flow
    • Bipartite matching is "no harder than" network flow
    • Bipartite matching ≤ Network flow
      • Reduce the problem of bipartite matching to the problem of network flow
      • How long does this take?
    • Edmonds-Karp specialization of Ford-Fulkerson Network Flow: O(VE^2)
      • Network Flow ∈ P
    • Then Bipartite matching ∈ P!
• P vs NP
  • P: class of problems for which a polynomial time algorithm exists
  • NP: class of problems that are verifiable in polynomial time
    • examples: IsSorted, Hamiltonian path, subset-sum
    • equivalent to class of problems for which a nondeterministic polynomial time algorithm exists
      • nondeterministic: can be thought of as "lucky" guessing
        • can make guesses in the algorithm
        • if there is a correct guess, you are guaranteed to choose it
  • P ⊆ NP
• NP-completeness
  • NP's "hardest problems" are NP-complete
  • 3SAT: boolean formulas for which satisfying truth assignment exists
    • conjunctive normal form with 3 literals per clause
      • (a OR b OR c) AND (d OR e OR f) AND ...
  • 3SAT is NP-complete
    • 3SAT ∈ NP
    • T ≤p 3SAT for all T ∈ NP [via Cook-Levin Theorem]
  • What about SUBSET-SUM?
    • Show 3SAT ≤p SUBSET-SUM:
      • Given boolean formula in 3CNF form
        • n variables
        • m clauses
        • CNF: conjunctive normal form
          • m clauses ANDed together
          • each clause is the OR of k=3 literals
            • a literal is a variable or its negation
      • Create a set of 2n + (k-1)m decimal numbers
        • each number has n + k digits
        • table schematic
          • rows are numbers
          • columns are digits
        • two types of columns
          • first n columns labeled by variables
          • last m columns labeled by clauses
        • two types of rows
          • 2n variable value rows
            • one row for variable x and one for negation !x
              • variable columns: 1 if column for x, 0 otherwise
              • clauses columns: 1 in column if clause contains literal, 0 otherwise
          • 2m [generally (k-1)m] "slack" rows
            • 2 rows for each clause c
              • variable columns: 0
              • clauses columns: 1 if column for c, 0 otherwise
      • target value is decimal number: n 1's, followed by m 3's
        • sum to 1 in variable columns <=> each variable assigned true or false
        • sum to 3 in clause columns <=> at least one literal certify truth
          • (may need to pad with slack variables)
    • example: B = (x or y or z) and (!x or y or !z)

      x  y  z  c1 c2

 x:   1  0  0  1  0           // x = T

!x:   1  0  0  0  1           // x = F

 y:   0  1  0  1  1           // y = T

!y:   0  1  0  0  0           // y = F

 z:   0  0  1  1  0           // z = T

!z:   0  0  1  0  1           // z = F

c1:   0  0  0  1  0           // slack for c1 if only <3 literals T

c1:   0  0  0  1  0           // slack for c1 if only <3 literals T

c2:   0  0  0  0  1           // slack for c2 if only <3 literals T

c2:   0  0  0  0  1           // slack for c2 if only <3 literals T

--------------------

 t:   1  1  1  3  3           

• summary: B reduces to { 10010, 10001, 1011, 1000, 101, 10, 10, 1, 1 }, target value 11133
  • solution to Subset-sum instance gives: {10, 10, 101, 1011, 10001}
  • corresponding to: both c1 slack rows, !z, y and !x
    • truth assignment is: x - F, y - T, z - F
    • clause 1 only has one true literal (y), so needs both slack rows to get to 3
    • clause 2 has all three literals (!x, y, !z), so uses no slack rows
• The big question... is P = NP?
  • Solving any NP-complete problem in polynomial time would show P = NP

Concepts

• Reduction from problem A to problem B
  • function f: A → B such that x ∈ A if and only if f(x) ∈ B
  • f converts a "yes" instance of A to a "yes" instance f(x) of b, and
  • f converts a "no" instance of A to a "no" instance f(x) of b, and
• A ≤p B
  • "reducible in polynomial time"
  • if there is a reduction that can be computed in polynomial time
• P: class of problems for which a polynomial time algorithm exists
• NP: class of problems that are verifiable in polynomial time
• Problem S is NP-hard if:
  • T ≤p S for all T ∈ NP
• Problem S is NP-complete if:
  • S ∈ NP
  • T ≤p S for all T ∈ NP