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