Rapport fra forelesningene

Jeg er nå ferdig med å forelese kap. 7. Nest uke begynner jeg å forelese kap. 8 (Space Complexity).

Denne uken har vi brukt mye av forelesningstiden til følgende: (1) p-redusere 3SAT til HAMPATH, (2) p-redusere 3SAT til SUBSET-SUM og (3) vise at SAT og 3SAT er NP-komplette språk.

Mvh

Lars