Skip to main content
MyCourses MyCourses
  • Schools
    School of Arts, Design, and Architecture (ARTS) School of Business (BIZ) School of Chemical Engineering (CHEM) –sGuides for students (CHEM) – Instructions for report writing (CHEM) School of Electrical Engineering (ELEC) School of Engineering (ENG) School of Science (SCI) Language Centre Open University Library 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
  • Service Links
    MyCourses - Instructions for Teachers - Teacher book your online session with a specialist - Digital tools for teaching - Personal data protection instructions for teachers - Instructions for Students - Workspace for thesis supervision WebOodi Into portal for students Courses.aalto.fi Library Services - Resourcesguides - Imagoa / Open science and images IT Services Campus maps - Search spaces and see opening hours Restaurants in Otaniemi ASU Aalto Student Union Aalto Marketplace
  • ALLWELL?
    Study Skills Support for Studying Starting Point of Wellbeing About AllWell? study well-being questionnaire
  •   ‎(en)‎
      ‎(en)‎   ‎(fi)‎   ‎(sv)‎
  • Toggle Search menu
  • Hi guest! (Log in)

close

CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017

  1. Home
  2. Courses
  3. School of Science
  4. department of...
  5. cs-e4530 - co...
Syllabus

General

  • General

    General

    

    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 General discussion Forum

Course home

Course home

Next section

Materials►
Skip Upcoming events
Upcoming events
Loading There are no upcoming events
Go to calendar...
  • CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017
  • Sections
  • General
  • Materials
  • Assignments
  • Home

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

Hi guest! (Log in)
  • Schools
    • School of Arts, Design, and Architecture (ARTS)
    • School of Business (BIZ)
    • School of Chemical Engineering (CHEM)
    • –sGuides for students (CHEM)
    • – Instructions for report writing (CHEM)
    • School of Electrical Engineering (ELEC)
    • School of Engineering (ENG)
    • School of Science (SCI)
    • Language Centre
    • Open University
    • Library
    • 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
  • Service Links
    • MyCourses
    • - Instructions for Teachers
    • - Teacher book your online session with a specialist
    • - Digital tools for teaching
    • - Personal data protection instructions for teachers
    • - Instructions for Students
    • - Workspace for thesis supervision
    • WebOodi
    • Into portal for students
    • Courses.aalto.fi
    • Library Services
    • - Resourcesguides
    • - Imagoa / Open science and images
    • IT Services
    • Campus maps
    • - Search spaces and see opening hours
    • Restaurants in Otaniemi
    • ASU Aalto Student Union
    • Aalto Marketplace
  • ALLWELL?
    • Study Skills
    • Support for Studying
    • Starting Point of Wellbeing
    • About AllWell? study well-being questionnaire
  •   ‎(en)‎
    •   ‎(en)‎
    •   ‎(fi)‎
    •   ‎(sv)‎