DD2446 Komplexitetsteori 6,0 hp

Det grundläggande målet inom komplexitetsteorin är att klassificera problem med avseende på hur mycket resurser som krävs för att lösa dem. Komplexitetsklasser är klasser av problem som i något avseende kräver "lika" mycket resurser för att lösa. De mest grundläggande resurserna som studeras är beräkningstid och minnesutrymme. Ett fullständigt problem för en komplexitetsklass är ett problem som kan ses som det svåraste inom klassen.

Följande områden behandlas: Komplexitetsklasserna L, NL, P, NP, PSPACE, etc. Reduktion och fullständighet. Cooks' sats. Approximerbarhet. Probabilistiska algoritmer. Interaktiva bevis (IP).

Efter genomgången kurs ska en elev kunna

• definiera grundläggande komplexitetsklasser såsom P, NP, PSPACE, L, NL, och NC.
• formulera fullständiga problem för respektive komplexitetsklass och visa problem fullständiga med hjälp av reduktioner.
• bevisa grundläggande satser om komplexitetsmått samt resonera om komplexitetsteoretiska begrepp.
• läsa forskningsartiklar inom området i detaljnivå motsvarande att förstå bidraget i stort men inte nödvändigtvis förstå alla detaljer.

Motsvarande en av kurserna 2D1352/DD1352 Algoritmer, datastrukturer och komplexitet eller 2D1354/DD2354 Algoritmer och komplexitet.

Meddelas senast 4 veckor före kursstart på kursens hemsida. Läsåret 07/08 användes. S. Arora and B. Barak Computational Complexity: A Modern Approach, Cambridge University Press.

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

• ÖVN1 - Inlämningsuppgifter, 6,0 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Inlämningsuppgifter (ÖVN1; 6 hp).

Jakob Nordström

• Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
• Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
• Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Diskuteras med kursledaren.

Kursen ges normalt på engelska om inte samtliga kursdeltagare kan svenska.
Kursen ges vartannat år.