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.