Upp till kursens hemsida.

2D1446, Komplexitetsteori period 3 2001/2002

Kursen är nu avslutad

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 x_i 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, 13x₁⁹x₃⁷ - 8x₇ + 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

Registrering

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

Examination

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)

Hederskodex

• 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.

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.