Upp till kursens hemsida.

# 2D1446, Komplexitetsteori period 3 2001/2002

## Kursen är nu avslutad

En preliminär kursanalys finns nu, baserad på kursnämndsmöte och enkätsvar.

## Senaste nytt

Some comments related to problem set 3 in answer to questions I have been asked.

• In problem 7 you should consider the prover to be unbounded. The fact that it is really enough that the prover is in PSPACE is a corollary of the result you are asked to prove, and therefore cannot be assumed to hold inititally (otherwise the proof becomes circular).
• In problem 1b, the optimization problem is to find smallest possible set H that intersects all the sets C in the input. The approximation algorithm should find a solution containing at most b times as many elements as the optimal hitting set.
• In cop and robber there is a case not covered by the rules. What happens if the robber moves to the hideout and the cop is already there? Let us say that in this case the cop wins. However, since the cop is required to move at every turn, he cannot just go to the hideout and stay there.
• I have made a silly mistake: In problem 7 I meant to say undirected graph, but in the beginning I say "undirected acyclic graph" which makes the problem a lot easier (further down I only say "undirected geaph"). You can still solve it for 4 points, but it is hardly one of the two hardest problems on the set then. If you are going for grade 6, then for those purposes you can solve problem 7 without using that the graph is acyclic and then consider the problem "hard". However, I will also consider problem 6 to be an officially "hard" problem. The idea is that this will only increase your chances of a really good grade.
• Problem 6 mentions polynomials in xi for i = 1,...,n modulo p. Consider a polynomial to be a sum of terms where each term is a coefficient and a product of variables (possibly with exponents on the variables). For instance, 13x19x37 - 8x7 + 3 is a polynomial modulo 17.

The article Algebraic Methods for Interactive Proof Systems by Lund, Fortnow, Karloff, and Nisan was covered 18 Feb.

Homework set 3 is now available. It is due on Feb. 28.

Homework set 2 is now available.

In the last three lectures we will talk a bit about cryptography (just an overview of some theoretical aspects), interactive proofs, and complexity of parallel computation.

There has been several requests that I switch to Swedish, and since that is officially the language the course is taught in I will do so. I still plan to use English for information, login messages, and problem sets. I hope that is OK with everyone. Otherwise let me know.

Some comments related to problem set 1 in answer to questions I have been asked.

• If a TM has k strings, then the delta function (or Delta relation for an NTM) dependes on the current symbol on each string, that is, on the current state and on k scanned symbols (see Definition 2.4 in Papadimitriou).
• Note that P and SPACE(n) are classes of languages (or, equivalently, of decision problems). They do not include functions that produce (possibly long) outputs.
• You may use the certificate version of NP when showing that a language is in NP (see Section 9.1 in Papadimitriou).

There is a typo in problem set 1, problem 8: the hint should refer to problems 2.8.4 and 2.8.5 in the book.

Thanks to Mattias Amnefelt the Lecture log now has pointers to copies of my lecture notes (such as they are).

Mattias Amnefelt and Fredrik Niemelä have volunteered to form a "kursnämnd". Comments and suggestions can either be brought to them or to me. I am happy to discuss any questions, comments, or suggestions you might have.

Homework set 1 is now available.

Välkommen till första föreläsningen måndag 14/1 kl 10 i E33. KursPM i pdf finns här.

Kursboken finns enligt uppgift på kårbokhandeln (som flyttat till Osquars backe 21) och kostar ca 735 kr.

Glöm inte att registrera er.

## Lärare

Kursansvarig är Mikael Goldmann som enklast nås via epost: migo@nada.kth.se.

## Registrering

Endast de teknologer som delfakulteten lagt in i Ladok som studerande på en kurs kan godkännas på kursen. Se alltså till att du är registrerad i Ladok. För doktorander vid andra institutioner än Nada gäller särskilda regler som finns här. Dessutom måste du, för att kursledaren ska kunna hålla reda på dina resultat, registrera dig i Nadas resultatrapporteringssystem. Detta görs med kommandot >>res checkin kplx02>> på någon av Nadas unixdatorer. Registrera dig så snart som möjligt! För din egen skull bör du också ge kommandot >>course join kplx02>>.

## Kurslitteratur

 Som kursbok används Papadimitriou, Computational Complexity, Addison-Wesley. Boken läses på egen hand under kursens gång. Föreläsningarna täcker endast en del av kursmaterialet. Läsanvisning: Kapitlen 1-3, 7-10, 11, 13 ingår. Kapitel 4 bör läsas för terminologi och definitioner. Beroende på vad som gås igenom under de sista två veckorna kan exempelvis kapitlen 12, 16, 17, 19 ingå.

## Schema

Observera att oregelbundenheter markerats med fetstil.
 vecka 3 F1 2002-01-14 Må 10-12 E33 F2 2002-01-16 On 13-15 E33 F3 2002-01-17 To 10-12 E33 vecka 4 F4 2002-01-21 Må 10-12 E33 F5 2002-01-23 On 13-15 E33 F6 2002-01-24 To 10-12 E33 vecka 5 F7 2002-01-28 Må 10-12 E33 F8 2002-01-30 On 10-12 E33 F9 2002-01-31 To 10-12 E33 Inlämning av uppgift 1 vecka 6 F10 2002-02-04 Må 10-12 Q12 F11 2002-02-07 To 10-12 E33 vecka 7 F12 2002-02-11 Må 10-12 E33 F13 2002-02-14 To 10-12 E34 Inlämning av uppgift 2 vecka 8 F14 2002-02-18 Må 10-12 E33 F15 2002-02-21 To 10-12 E34 vecka 9 2002-02-28 To kl 16 Exp/Postfack Inlämning av uppgift 3

## Examination

Kursen examineras med inlämningsuppgifter som lämnas ut i tre omgångar. Uppgifterna kan lösas enskilt eller i grupper med två personer (men lämna varsin lösning och ange den andra gruppmedlemmen). Lösningarna ska även redovisas muntligt på speciella pass som ligger utanför ordinarie schema.

Får man minst 30% av full poäng på varje enskild omgång är man garanterad minst betyg 3. För högre betyg gäller dels minst 30% av maxpoäng på varje omgång, dels totalt 45% för 4, 60% för 5. På varje omgång kommer det att finnas en eller ett par problem av överkurskaraktär. För betyg 6 krävs 80% av maximal poäng och att man klarat flertalet av överkursproblemen. För studenter på SU gäller att kraven för G är desamma som för betyg 3, och för VG gäller dessutom totalt minst 53% av maximal poäng. Observera att "överkursuppgifterna" ger poäng på samma sätt som övriga uppgifter och att deras poäng räknas med i totalpoängen.

## Föreläsningar (preliminärt)

Nedan finns ett preliminärt schema. Dessutom finns här en föreläsningslog som kortfattat beskriver vad som gjorts på respektive föreläsning.
F1-3 Administration. Introduktion till komplexitetsteori och komplexitetsklasser. Beräkningsbarhet och beräkningsmodeller. Tids- och minneskomplexitet. (Kapitel 1-3) Komplexitetsklasser (P, NP, coNP, L, NL, PSPACE), reduktioner och fullständiga problem (kapitel 7-10 i ordning samt Theorem 19.1, ej 8.3), Algoritmer med slump (kapitel 11), approximationsalgoritmer och approximerbarhet (kapitel 13). Fördjupning inom några områden, förslagsvis parallell komplexitet och interaktiva bevis. Kom gärna med egna förslag och önskemål!

## Hederskodex

Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter, tentor m.m.) ska du göra själv. Ibland, speciellt när man skriver program, kan det vara nödvändigt att fråga någon annan (en kamrat eller en handledare) om hjälp med att hitta fel. Detta är tillåtet förutsatt att du uppfyller följande villkor.
• Om du fått hjälp med mer än bara någon enstaka rad i programmet ska du ge ett skriftligt erkännande till den som hjälpte till, lämpligen i form av en kommentarrad överst i programmet, som talar om vem som hjälpt dig med vad.
• Du måste förstå hela den färdiga lösningen, även de delar du fått hjälp med.
Varje annan form av samarbete och utnyttjande av andras lösningar betraktas som ett brott mot hederskodexen och kan bestraffas, t ex genom att du förlorar alla bonuspoäng eller får göra en ny uppgift. Allvarliga brott mot kursens regler eller hederskodexen rapporteras till institutionens prefekt.

Detta är en översatt och omarbetad version av den hederskodex som används i kursen Introduction to computer science vid Stanford University. Den tillämpas i många av Nadas kurser.

För den här kursen gäller att man får lösa inlämningsuppgifter i grupper med två personer (att lösa dem individuellt går också bra), men alla ska skriva en egen lösning med egna ord där det ska framgå vilka som ingår i gruppen. Om ni utnyttjar resultat, bevis eller ideer från kurslitteraturen eller någon annan källa så ange tydlig referens. Så länge man spelar med öppna kort kan det aldrig bli frågan om fusk.

En utförligare version av reglerna finns här.

Till sist, undvik att lägga era lösningar publikt tillgängliga, speciellt före inlämningsdatum, men gärna även därefter.

Upp till kursens hemsida.