11. NP-fuldstændighed
*********************

polynomielle vs. ikke-polynomielle problemer
afgørlighedsproblem
kodning af inddata, effektiv kodning
alfabet of sprog L
sprog L accepteres/afgøres af algoritme A
accept i polynomiel tid
definition af klassen P
verifikation, certifikat, verifikation i polynomiel tid
definition af klassen NP
P er en delmængde af NP
reduktion mellem sprog, herunder evt. transitiv egenskab
definition af NP-fuldstændige problemer
diskussion af klasserne P, NP, NPC, evt. også co-NP


12. Et NP-fuldstændighedsbevis
******************************

definition af NP-fuldstændigt problem, herunder forklare reduktion, NP, m.m.
bevisførelse af NP-hårdhed ved reduktion fra allerede kendt NPC problem
nævne at CIRCUIT-SAT tilhører NPC
afhængigt af ambitionsniveau kan man f.eks. vise to reduktioner:
- HAM-CYCLE og TSP er NP-fuldstændige
- CLIQUE og VERTEX-COVER er NP-fuldstændige


13. Branch-and-bound
********************

for hvilke problemer anvendes branch-and-bound?
definer NP-hårdhed for optimeringsproblemer
brute-force metoden og divide-and-conquer
grænseværdier herunder definition af en relaksering (vis gerne et
  eksempel)
branch-and-bound algoritmen (grænseværditest, øvre grænseværdi,
  nedre grænseværdi, søgestrategi, forgreningsregel).
afslut eventuelt med et af følgende emner: dominans af grænseværdier,
  kritiske og semi-kritiske delproblemer, eller et eksempel på en 
  branch-and-bound algoritme


14. Approximationsalgoritmer
****************************

for hvilke problemer anvendes approximationsalgoritmer?
findes altid en approximationsalgoritme?
definition af ratio bound for min og max problem
nævne relation mellem ratio bound og relativ fejl
definere PA, AS, PTAS, FPTAS
afhængigt af ambitionsniveau kan man f.eks. vise:
- VERTEX-COVER, TSP med trekantsulighed, TSP uden trekantsulighed


15. Fuldt polynomiel-tids approximationsskema
*********************************************

for hvilke problemer anvendes approximationsalgoritmer?
definition af ratio bound for min og max problem
definition PA, AS, PTAS, FPTAS
findes der FPTAS for alle problemer?
vis et FPTAS for subset-sum
- definer problemet
- skitser eksakt algoritme baseret på merge-list
- indfør trimning
- skitser hele algoritmen
der er næppe tid til at vise såvel relativ fejl og køretid,
  så vis kun et af disse og vær forberedt på spørgsmål i det andet.
evt. diskussion af om køretiden er polynomiel