Komplexitetsteori
Kursplan, Avancerad nivå, 1MA047
Kursen är avvecklad.
- Kod
- 1MA047
- Utbildningsnivå
- Avancerad nivå
- Huvudområde(n) med fördjupning
- Matematik A1N
- Betygsskala
- Med beröm godkänd (5), Icke utan beröm godkänd (4), Godkänd (3), Underkänd (U)
- Fastställd av
- Teknisk-naturvetenskapliga fakultetsnämnden, 15 mars 2007
- Ansvarig institution
- Matematiska institutionen
Behörighetskrav
Kandidatexamen samt Logik II och Automatateori eller motsvarande.
Mål
För godkänt betyg på kursen skall studenten
Innehåll
Algoritmbegreppet. Maskinmodeller för beräkningar: varianter av Turingmaskiner och ekvivalens mellan dessa. Komplexitetsteori: komplexitetshierarkier, effektiv reducerbarhet, P=NP-problemet, NP-fullständiga problem, komplexitet av avgörbarhetsproblem från logik och automatateori. Savitchs sats. Polynomiella hierarkin. Booleska funktioner och kretsar. Logisk komplexitet i första och andra ordningen och dess förhållande till komplexitetsklasser. Relativiserade P=NP-problemet. Probabilistiska algoritmer och komplexitetsteori för dessa. Undre gränser för bevislängd i satslogiska system. Komplexitet för andra beräkningsmodeller som exakt reell aritmetik, funktionaler av högre typ, och kvantberäkningar.
Undervisning
Föreläsningar och räkneövningar
Examination
Skriftligt och eventuellt muntligt prov vid kursens slut eventuellt kombinerat med inlämningsuppgifter under kursen enligt anvisningar som lämnas vid kursens start.