Hva vil skje på forelesningene denne uken?

Fra Lars:

God mandag morgen. Denne uken vil vi bruke mye av forelseningstiden på beviset for at SAT (3SAT) er NP-komplett (jeg rakk ikke å forelese dette beviset  forrige uke slik jeg oprinnelig hadde satt meg fore). Det er et langt og vanskelig bevis. Oppgaver som skal løses denne uken finner dere på listen nedenfor.

Vi vil også bruke litt forelesningstid tid på beviset for at 3SAT er polynom-tid reduserbart til SUBSET-SUM, men detaljene  i beviset vil bli gått gjennom i gruppeundervisningen.