Computational Complexity

Antal poäng: 5.0. Valfri för: D4. Kursansvarig: Rolf Karlsson Förkunskapskrav: godkänt betyg i EDA 025 Algoritmer och datastrukturer. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Övrigt: Kursen ges i samarbete med Datalogi och numerisk analys, mat. nat. fak.

Jfr EDA 153, det lägre poängtalet erhålls när också EDA 140 Formella språk och automater ingår i examen.

Innehåll

Syfte. Att ge kunskap om den matematisk-logiska grund som utvecklats för förståelse och analys av datorers möjligheter och begränsningar vid problemlösning. Komplexitet betraktas som samspelet mellan beräkning (komplexitetsklasser) och tillämpningar (problem).

Turingmaskiner och oavgörbarhet. Komplexitetsklasser. Reduktioner och fullständighet. NP-fullständiga problem. Randomiserad beräkning. Interaktiva bevis. Approximationsalgoritmer. Polynomiska hierarkin. PSPACE och spelkomplexitet.

Litteratur

Papadimitriou, C. H.: Computational Complexity. Addison-Wesley 1994.