[an error occurred while processing this directive]
Kretskomplexitet 2003
[an error occurred while processing this directive]
Kurs i kretskomplexitet
Inom kretskomplexitet studerar man storleken och djupet hos kretsar
som löser olika beräkningsproblem. Kretskomplexitet har studerats som
en möjlig väg att angripa P-vs-NP-problemet, men har även använts som
ett verktyg inom bland annat "Computational learning theory",
kryptografi och beviskomplexitet.
Kursen syftar till att ge en grundlig introduktion till området, och
tonvikten kommer att ligga på resultat från 80- och tidigt 90-tal då
området utvecklades snabbt. Om tid ges och intresse finns kommer även
intressanta resultat från de senaste åren att tas upp.
Kursen ger 4p
Hemtal
Nu finns hemtalet i
postscript
och
pdf. Deadline är 20/1 2004.
Schema
Vi kommer att träffas två gånger i veckan på följande tider och
platser:
Fredagar 13-15 i rum 4523: 24/10, 31/10, 7/11, 14/11, 21/11, 28/11,
5/12 (kl 13-16), 12/12, 19/12.
Tisdagar 15-17 i rum 1537: 28/10, 4/11, 11/11, 18/11, 2/12, 16/12.
Tisdag 25/11 och 9/12 kl 15-17 i rum 4523.
Litteratur
Wegener: The complexity of boolean functions. Finns på nätet. Googla på
författare och titel!
Examination
Endast betyg G. Examination genom inlämningsuppgifter och
presentationer. Meningen är att deltagarna ska turas om att hålla
föreläsningar, men Johan och Mikael kommer att hålla en del av
föreläsningarna också.
Prelimär planering
Introduktion. Kretsfamiljer. Kretskomplexitet vs
Turingmaskinkomplexitet. Likformiga och olikformiga
komplexitetesklasser.
Shannon-gränser.
NC och AC. Exempel på kretsar för addition och multiplikation.
