Introduction to Computation and complexity

• factoring : NP

  palindrome : P

  sumOfParities : P

  Halt : none

  winning strategries : EXP
• regular language is in SPACE(n)

  palindrome is in SPACE(n)

  sum (a,b,c) is in SPACE(log(n))
• P included in PSPACE because every polynomial runtime copmutation can only exhaust a polynomial number of tape cells
• NP included in PSPACE because if A in NP, we can re-use tape space to cycle through all possible short certificates to decide wheter x in A or not in A
• PSPACE included in EXP because there are 'only' exponentially many TM configurations to visit throughout the course of computation
• • 3-SAT : NP co-NP
  • palindrome : P
  • TQBF : PSPACE
  • Factoring problem : NP co-NP
  • optimaly strategy for boolean 2-player : PSPACE
• contained in co-np:

  • tautology
  • factoring
  • graph - non - ismorphism
• CNF

  size 2k-1 = O(mk)

  depth log_2(k) + log_2(m) = O(log(km))
• DNF : connected by OR

  CNF : connected by AND
• Toffoli gate :

  • NOT(x) = T'(1,1,x)
  • OR(x,y) = T'(1, y, T'(x,y,z))
  • AND(x,y) = T(x,y,0)
• P included in PSIZE
• PSIZE contains the unary halting problem while NP doesn't