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
skitser ideen i branch-and-bound (systematisk gennemsøgning af hele
  løsningsrummet hvor grænseværdier bruges til at undgå visse delproblemer)
elementer af branch-and-bound algoritmen (minimeringsproblem, "incumbent" 
  løsning, opdeling af løsningsrum, grænseværdi, forkastning af delløsningsrum)
udledning af grænseværdier (relaxering og/eller modifikation af objektfunktion)
søgestrategier og deres fordele/ulæmper 
  (bredde-først, dybde-først, bedste-først)
kritiske og semi-kritiske delproblemer
afslut evt. med 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