COMPSCI 750: Computational Complexity

COURSE DETAILS

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

It discusses Turing machines, the complexity classes P and NP, Cook-Levin Theorem, NP-completeness, space complexity, BPP and randomised algorithms,  and special topics on algorithmic and quantum  randomness and quantum computing.

 

No lecture on Monday,  July 16. 

LECTURES:  

Mo 10-11 AM  114-G18 (Commerce A, Room G18)  

Th 2-3 PM   303-G13 (Sci Maths & Physics, Room G13)

Fr 11-12 AM 303-610 (Sci Maths & Physics, Room 610)

 

 

TEACHING STAFF

Andre Nies,

Weeks 1-6 Office 303-421

andre@cs.auckland.ac.nz

Office hours: Th 3-4

 

 

Cristan Calude

Weeks 7-12

c.calude@auckland.ac.nz

Office hours by appointment

 

Class Rep: TBA

 

Text required: Michael Sipser, Introduction to the theory of computation, 2d or 3d edition

 

 ISBN13: 978-1-133-18779-0

 

 

ASSESSMENT

50% exam; 20% test; 30% assignments