Rapport fra forelesningene

Denne uken har vi snakket om NP og NP-komplette språk. Vi har vist at k-CLIQUE og HAMPATH er i NP. Vi har vist at at 3SAT er polynom-tid reduserbart til k-CLIQUE.

Neste forelesning vil jeg bruke en del tid på vise at 3SAT er polynom-tid reduserbart til HAMPATH. Dette er et vanskelig bevis som vi skal gå grundig gjennom. Det kan være en god ide å forberede seg ved å lese sidene 314-318 i læreboken. Deretter vil jeg gå grundig gjennom  bevisene for at språkene SAT og 3SAT er NP-komplette. Dette er også vanskelige bevis, og  det kan være en god ide å forberede seg  ved å lese litt i læreboken før man kommer på forelesning.  Deretter vil se på flere NP-komplette språk (SUBSET-SUM, UHAMPATH). Jeg regner med å gjøre meg ferdig med å forelese kapittel 7 i løpet av de to-tre  neste forelesningene.

God påske

Lars