Gå direkt till huvudinnehåll
MyCourses MyCourses
  • Högskolor
    Handelshögskolan (BIZ) Högskolan för elektroteknik (ELEC) Högskolan för ingenjörsvetenskaper (ENG) Högskolan för kemiteknik (CHEM) – Andra guider (CHEM) – Anvisning för literaturarbeten (CHEM) Högskolan för konst, design och arkitektur (ARTS) Högskolan för teknikvetenskaper (SCI) Andra studier Språkcentret Open University Biblioteket Aalto university pedagogical training program UNI (exams) Sandbox
  • CORONAVIRUS INFO
    Koronavirus - tietoa opiskelijalle Coronavirus - information for students Coronavirus - information för studerande Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia Effects of the coronavirus on studies: questions and answers Coronaviruset och studierna: frågor och svar Corona help for teachers
  • Länkar till tjänster
    MyCourses - Instructions for Teachers - Teacher book your online session with a specialist - Digital tools for teaching - Data protection instructions for teachers - Anvisningar för studerande - Workspace for thesis supervision WebOodi Into studentportal Courses.aalto.fi Unverisitets bibliotek - Resourcesguides - Imagoa / Öppen vetenskap och användning av bilder IT-tjänster Campus - Byggnads öppettider Restaurants in Otaniemi AUS Aalto-universitetets studentkår Aalto Marketplace
  • ALLWELL?
    Studiekompetens Stöd för studerande Starting Point of Wellbeing Om AllWell? -enkäten
  •   ‎(sv)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Du är för tillfället inloggad som gästanvändare (Logga in)

close

CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017

  1. Framsida
  2. Kurser
  3. högskolan f?...
  4. department of...
  5. cs-e4530 - co...
Kursens beskrivning

Allmänt

  • Allmänt

    Allmänt

    

    Course Information


    Lectures

    Mondays and Wednesdays 10-12 T3
    First lecture: 9th January

    Classroom sessions

    Tuesdays 14-16 A211
    First session; 17th January

    Lecturer

    Chris Purcell

    Teaching Assistants

    Janne Korhonen, Tuomo Lempiäinen

    Topics

    Models of computation: Turing machines, RAM machines, Boolean
    circuits
    Modes of computation: deterministic, nondeterministic, parallel,
    randomised, alternating
    Basic notions of computational complexity: complexity measures and
    complexity classes, hierarchy theorems, reductions between problems,
    completeness
    Central complexity classes: P, NP, PSPACE, NC, polynomial time
    hierarchy, etc.
    Design of completeness proofs, especially for NP-completeness
    Applications and extensions: approximability, counting, games,
    cryptographic protocols

    Learning Outcomes

    Once you have taken the course, you master the key complexity
    classes, their underlying models of computation, and
    relationships.
    You are able to formalise and abstract from a given computational
    task relevant computational problems and argue that they belong
    to appropriate complexity classes.
    You understand the concept of reductions and how it can be used
    to order problems by their computational complexity. You are able
    to show using reductions that a problem is complete for a central
    complexity class (such as NP) and you understand the
    importance and implications of such a result.
    You are familiar with the concepts of randomised, approximation,
    and parallel computation and aware of related complexity classes
    and their relation to other complexity classes and their models of
    computation.

    • icon for activity News forum
    • icon for activity Allmän diskussion Forum

Course home

Course home

Nästa sektion

Material►
Hoppa över Kommande händelser
Kommande händelser
Laddar Det finns inga framtida händelser
Gå till Kalender
  • CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017
  • Sektioner
  • Allmänt
  • Material
  • Uppgifter
  • Framsida

Aalto logo

Tuki / Support
  • MyCourses help
  • mycourses(at)aalto.fi
Palvelusta
  • MyCourses rekisteriseloste
  • Tietosuojailmoitus
  • Palvelukuvaus
About service
  • MyCourses protection of privacy
  • Privacy notice
  • Service description
Service
  • MyCourses registerbeskrivining
  • Dataskyddsmeddelande
  • Beskrivining av tjänsten

Du är för tillfället inloggad som gästanvändare (Logga in)
  • Högskolor
    • Handelshögskolan (BIZ)
    • Högskolan för elektroteknik (ELEC)
    • Högskolan för ingenjörsvetenskaper (ENG)
    • Högskolan för kemiteknik (CHEM)
    • – Andra guider (CHEM)
    • – Anvisning för literaturarbeten (CHEM)
    • Högskolan för konst, design och arkitektur (ARTS)
    • Högskolan för teknikvetenskaper (SCI)
    • Andra studier
    • Språkcentret
    • Open University
    • Biblioteket
    • Aalto university pedagogical training program
    • UNI (exams)
    • Sandbox
  • CORONAVIRUS INFO
    • Koronavirus - tietoa opiskelijalle
    • Coronavirus - information for students
    • Coronavirus - information för studerande
    • Koronaviruksen vaikutus opiskeluun: kysymyksiä ja vastauksia
    • Effects of the coronavirus on studies: questions and answers
    • Coronaviruset och studierna: frågor och svar
    • Corona help for teachers
  • Länkar till tjänster
    • MyCourses
    • - Instructions for Teachers
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Data protection instructions for teachers
    • - Anvisningar för studerande
    • - Workspace for thesis supervision
    • WebOodi
    • Into studentportal
    • Courses.aalto.fi
    • Unverisitets bibliotek
    • - Resourcesguides
    • - Imagoa / Öppen vetenskap och användning av bilder
    • IT-tjänster
    • Campus
    • - Byggnads öppettider
    • Restaurants in Otaniemi
    • AUS Aalto-universitetets studentkår
    • Aalto Marketplace
  • ALLWELL?
    • Studiekompetens
    • Stöd för studerande
    • Starting Point of Wellbeing
    • Om AllWell? -enkäten
  •   ‎(sv)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎