CompSci 260P: Week 4

NP-Completeness ... Again Again

Ryuto Kitagawa

Sharing Problem

  • Given non-negative integers
  • Can the numbers be split into two sets, and with the same sum?
    • Each element can only appear in one set
  • Is this problem NP-Complete?

Sharing is NP

  • Verifying should take at most time
  • Up to you guys to figure out how

Sharing is NP-Hard

  • Unknown: Sharing
  • Known: ... ?
    • Subset Sum!
  • Intuition
    • We know the target sum is for subset sum
    • We want the two sets we create to equal (ish)
    • How do we force that to occur?

Sharing -> Subset Sum

  • To use Sharing to solve Subset Sum:
    • Calculate
    • Create
    • Run Sharing with

No False Positives

  • Claim: If Sharing returns true, the original Subset Sum should also return true
  • If
    • One partition has
    • The other partition must add up to
  • If
    • One partition has adds up to

No False Negatives

  • Claim: If Subset Sum returns true, Sharing should also return true
  • If
    • Solution from Subset Sum is used to create one partition
    • Everything else belongs in the other partition
  • If
    • Do the same but in reverse

Common Mistake

  • Only solving a specific case of another problem
  • Ex. using Sharing to solve Subset Sum when

Inner Circle Problem

  • Faculty committee with members voting on issues
  • Votes: "Yes", "No", or "Abstain"
  • Issue passes if more "yes" than "no" votes
  • Inner Circle: Subset of professors () whose votes determine the result for every issue
  • Goal: Determine if there is an inner circle of size

Inner Circle is NP

  • Again, should be simple

Inner Circle is NP-Complete

  • Unknown: Inner Circle
  • Known: ... ?
    • Consider that Inner Circle finds a group of size at most
    • Several problems that are like this
    • In this example we will use vertex cover

Inner Circle -> Vertex Cover

  • Inner Circle is finding faculty members
    • Each vertex -> faculty member
  • Inner Circle includes faculty members with relevant votes
    • Each edge -> issue where faculty members vote yes
    • Everyone else abstains
  • A vertex cover of size exists iff an inner circle of size exists

No False Positives

  • Claim: If Inner Circle returns true, there is a vertex cover of size
  • Inner circle's votes determine the results
    • Each issue only has two voters, if both abstain then not an inner circle
    • Thus at least one of them must be included
    • Analagous to the vertex cover

No False Negatives

  • Claim: If a vertex cover of size exists, Inner Circle returns true
  • For each edge, at least one endpoint is in the cover
  • For each issue, we only need one of the two members that said "yes"
  • We will have that from the vertex cover