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