Behörighetskrav

120 högskolepoäng samt Logik II och Automatateori eller motsvarande.

Mål

Efter godkänd kurs ska studenten kunna

• redogöra för algoritmbegreppet;
• redogöra för olika maskinmodeller för beräkningar och deras inbördes förhållande;
• redogöra för robusthetsegenskaper hos komplexitetsklassen P och kunna redogöra för P = NP problemet;
• utföra reduktioner av fullständiga problem till förelagda problem, exempelvis SAT till CLIQUE;
• redogöra för hierarkisatserna;
• redogöra för fullständiga problem inom olika komplexitetsklasser;
• redogöra för huvuddragen i beviset av Cook-Levinsatsen;
• redogöra för vissa probabilistiska algoritmer, exempelvis primtalsalgoritmen;
• redogöra för de vanliga probabilistiska komplexitetsklasserna;
• använda teorin för att lösa problem kring komplexitetsfrågor som uppstår i matematik eller datavetenskap.

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.