Computer Science


Computational Complexity: COMPSCI 750


Taught: Second semester, three lectures per week

Prerequisites: CompSci 320 or CompSci 350 or equivalent

Assessment: 60% exam; 20% test; 20% assignments

Lecturers:

Professor Andre Nies. Room 303-421

Description: This is a survey paper on computational and descriptive complexities and applications.

Content: Turing machines, the classes P and NP, Cook-Levin Theorem, NP-completeness, Space complexity, Intractability, Randomized algorithms, Boolean circuits, Quantum Computing.

Archived material: Calude's 2016 Time complexity slides, Calude's 2016 Quantum computing slides.

Highly recommended for all graduate students interested in theoretical computer science.

Please check the CANVAS course page for more information.


Apply now!


Handbook

Postgraduate study options

Computer Science Blog



Please give us your feedback or ask us a question

This message is...


My feedback or question is...


My email address is...

(Only if you need a reply)

A to Z Directory | Site map | Accessibility | Copyright | Privacy | Disclaimer | Feedback on this page