10 - Space complexity

• memory


  space-bounded computations
• PSPACE polynomial space/memory requirements seem to be less stringent than for polynomial running time.
• space-bounded computation like SPACE(f(n)) are based on a maximum number of O(f|x|) non-blank tape symbols
• Landscape of complexity classes

  A) P

  B) NP

  C) PSPACE

  D) EXP

  
• Space-bounded computations are at least as powerful as time-bounded ones

  A) f(n)

  B) language

  C) implies

  
• PSPACE contains all languages that can be decided using polynomial space (in input size)
• NSPACE

  if there is a nondeterminstic TM that decides x in A based on trajectories that all use at most O(f(|x|)) non-blank tape symbols
• Savitch' s theorem

  NPSPACE = PSPACE
• PSPACE = NPSACE

  A) =<

  B) hard

  C) NP-complete

  
• QBF


  Quantifiers first and then the clauses
• Fact

  A) CNF

  B) satisfiable

  C) true

  D) 1

  
• TQBF 


  a fully quantified boolean formula in the form of a QBF evaluates to 1
• TQBF contained in PSPACE
• TQBF can be used as an optimal strategy in a 2-player game (with perfect knowledge)
• Determining whether the 2-player QBF game introduced above has an optimal winning strategy is PSPACE complete