NP

Return to List of Lectures

Previous Lecture

• Misc
  • REU Talk
    • “Monotone Catenary Degree in Numerical Monoids”
    • Jenna Zomback
    • Thursday, Nov. 12, 3:30, Newton 212
    • Extra credit as usual
  • CIT hiring a student web assistant for spring
    • Help develop/maintain college web pages; programming not required but possible if interested
    • Contact Paul Jackson (jackson@geneseo.edu) to apply or for more info
• Questions?
• The Class NP
  • Summary of section 34.2
    • Hamiltonian cycle = simple cycle containing each vertex
      • Derived from game on dodecahedron?
        • Idea is to represent adjacency of vertices of a dodecahedron as a graph
          
      • Problem = does G have Hamiltonian cycle?
        • # vertices is roughly √n
        • So brute-force search of all permutations of vertices to see if any is a cycle can solve problem in time Ω(√n!) = Ω(2^√n)
    • Verification algorithms
    • Does P = NP?
      • Compelling evidence coming up that the classes might be equal
        • Note: this isn’t how most people interpret the evidence, so look at it as we get to it and see what it tells you
    • Relationships between P, NP, etc. are neat
    • Is NP closed under complement?
  • Graphs and Hamiltonian cycles
    • Graph = Edges and nodes aka vertices
      • Vertices are nouns
      • Edges are ordered pairs of nodes, imply relation or connection
        
  • Examples
    • PARTITION: Set partitioning (input = set of numbers S, accept iff S = S₁ ∪ S₂ (disjoint) such that sum of numbers in S₁ = sum of numbers in S₂)
      

      Verifier( S, S1 )
          Calculate sum of elements in S1
          Calculate sum of elements in S - S1
          Accept if sums are equal

    • COMPOSITE (input is a natural number n, accept if n has non-trivial factors)
      

      Verifier( n, f )
          accept if n mod f = 0

      • Long division algorithm can be used to run this in polynomial time
• The Class Co-NP
  • Co-NP = problems whose complements are in NP
  • P′ = complement of problem P:
    • Domain of P is D
    • S is the subset of D that P accepts
    • P′ accepts D - S
  • Examples?
    • PRIME = complement of COMPOSITE
      • PRIME has a polynomial time solution, so this example shows that P and Co-NP are non-disjoint
    • PARTITION′ = given set S, is there no partition into S₁ and S₂ such that sum of elements in S₁ = sum of elements in S₂
      • Not obviously in NP
        • First thought about a verifier that takes all partitions as certificate doesn’t run in polynomial time
      • So this is an example of how Co-NP might (but also might not) be distinct from NP
• Problem Set
  • Handout
• Next
  • Reducibility
  • Read section 34.3 through “Reducibility” (pages 1067 and 1068)

Next Lecture