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...
  6. Sections
  7. Materials
Syllabus

Materials

  • Materials

    Materials

    • icon for activity Lecture 1: Introduction File PDF document
    • icon for activity Lecture 2: Turing Machines File PDF document
    • icon for activity Lecture 3: Nondeterminism, RAM model File PDF document
    • icon for activity Lecture 4: Universal Turing Machines and Undecidability File PDF document
    • icon for activity Midterm Practice Questions File PDF document
    • icon for activity Lecture 5: Boolean logic File PDF document
    • icon for activity Lecture 6: Complexity classes File PDF document
    • icon for activity Lecture 7: Reductions and Completeness File PDF document
    • icon for activity Lecture 8: NP-complete problems File PDF document
    • icon for activity Lecture 9: co-NP, the structure of NP and relativization File PDF document
    • icon for activity Lecture 10: Polynomial Hierarchy and Alternations File PDF document
    • icon for activity Lecture 11 Circuit complexity and parallel computing File PDF document
    • icon for activity Lecture 12: Randomised computation File PDF document
    • icon for activity Lecture 13: Cryptography File PDF document
    • icon for activity Lecture 14: Approximability File PDF document
    • icon for activity Exam Practice Questions File PDF document
    • icon for activity Lecture 15: Counting, PSPACE, and beyond File PDF document

Course home

Course home

Next section

Assignments►
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)‎