Higher Complexity Classes and Coping with Intractability

Return to List of Lectures

Previous Lecture

• Misc
  • SOFIs
    • Helpful to me in teaching this (or other) courses in future
    • Access through myGeneseo/KnightWeb
  • Final
    • Wednesday, Dec. 16, noon
    • Comprehensive, but emphasizing material since 2nd hour exam (e.g., complexity classes, NP completeness)
    • Designed for 2 hours,you have 3
    • Otherwise similar rules and format to hour exams, particularly open-references rule
    • Donuts & cider
• Questions?
  • Integer programming question on problem set: can reduce from 0-1 integer programming
• Complexity Beyond NP
  • Polynomial space (PSPACE)
    • Memory space required to solve problem polynomial in input size
    • e.g., show that SAT is in PSPACE
      • An algorithm for SAT that runs in polynomial space:
        

        given formula f with variables x1 … xn
        
        let v be an n-element vector of logical values
        for each combination of n truth values
            store it in v
            check if f is true

    • So how does NP relate to PSPACE?
      • NP ⊆ PSPACE
      • Because all problems in NP can be reduced in polynomial time and therefore polynomial space to SAT, which can be solved in at most an additional polynomial amount of space
    • There exist PSPACE complete problems
      • Canonically, TQBF (True Quantified Boolean Formulas)
        • ∀a₁,a₂,…∃b₁,b₂,…∀c₁,c₂,… Φ(a₁,a₂,…,b₁,b₂,…,c₁,c₂,…)
        • For example
          • ∀x∃y x∧y — not in TQBF
          • ∀x∃y x∨y — in TQBF
      • Also many games, e.g., (generalizations to arbitrary board sizes of) go, checkers, chess
  • Exponential time (EXPTIME)
    • Time in O( 2^nk )
  • Relationships
    • P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
    • P ≠ EXPTIME
    • Nobody knows where the proper subset is!
• Coping with Intractability
  • Approximation algorithms
    • Algorithms that come close to a solution to an optimization problem
    • Some have provable bounds on ratio of approximate solution cost to optimal cost
  • Solvers
    • Algorithms (or heuristics) that usually run quickly but may take exponential time in pathological cases
    • Especially SAT
    • The “universal solver” for NP hard problems - why?
      • Because everything in NP reduces to it reasonably quickly and without fatal increases in problem size
    • e.g., backtracking SAT solver
      • Simplified form of “DPLL solver”
        

(No Next Lecture)