11 - co-NP and the polynomial hierarchy

• Landscape of complexity classes

  A) EXP

  B) PSPACE

  C) co-NP

  D) NP

  E) P

  
• prime factorization

  
• AKS primality test

  a polynomial-time alogrithm that decides the langauge Primes = {F : F is a prime number} in {0,1}*
• co-NP


  a lanauge is in co-NP if its complement is contained in NP
• co-NP is not the complement of the problem class NP -> nontrivial intersection
• THe intersection between NP and co-Np contains some languages for which we don't know any efficient algorithm
• tautologie

  1 for all input x
• Tautology

  A) co-NP

  B) co-NP

  C) polynomial-time reduction

  D) =<_p

  
• unless NP = co-NP, factoring cannot be NP-complete
• NP, co-NP more symmetric

  A) polynomial runtime

  B) polynomial

  C) exists

  D) forall

  
• negation of there exists -> forall
• Problem class sommation_i ^p

  A) exists

  B) forall or exists

  C) parity

  
• Problem class

  A) polynomial

  B) forall

  
• $\sum_1^p$= NP

  $\Pi_1^p$= co-NP

  $\sum_0^p =$$\Pi_0^P =$P
• Polynomial hierachy

  A) PSPACE

  B) co-NP

  C) NP

  D) P

  E) pip2

  F) sump2

  
• Polynomial hierarchy PH

  A) i >= 0

  
• for each i >= 1, sum and pi are distinct
• if sum and pi not distrinct -> polynomial hierarchy collapses to the i-th level
• If facotring is NP-complete, the nthe polynomial hierarchy collapses to the first level (i=1) $PH =$$\sum_1^p =$$NP$