Oppdatering

Vi har sett eksempler på hvordan et språk A kan polynom-tid reduseres til et språk B. Man bør øve seg på
å beskrive polynom-tid reduksjoner mellom NP -komplette språk.

Nest uke  vil jeg først snakke mer om beviset for Theorem 7.35 (SAT er NP-komplett) og beviset for Corollary 7.42 (3SAT er NP-komplett). Deretter vil jeg begynne å forelese Chapter 8.