COURSE DETAILS

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

Weeks 1-6  introduce descriptive complexity, algorithmic randomness and a form of quantum randomness followed by a brief theoretical and practical introduction to quantum computing which includes the quantum gates and adiabatic models and applications.

Weeks 7-12 cover the complexity classes P and NP, NP-completeness, space complexity, intractability, BPP and randomised algorithms,  and   more detail on theoretical quantum computing: mathematical background, BQP, Shor's factoring  algorithm.

LECTURES:  

Tu 16:00 - 17:00 Commerce A, Room G14

Th 14:00 - 15:00 303-G15

Fr 16:00 - 17:00 Commerce A, Room G01

TEACHING STAFF

Cristian S. Calude

Weeks 1-6

cristian@cs.auckland.ac.nz

Office hours by appointment

Andre Nies,

Weeks 7-12  Office 810-847 in Short Street

andre@cs.auckland.ac.nz

Office hours: Tu 2:30-3:30

Class Rep: TBA

Useful text: Michael Sipser, Introduction to the theory of computation, 2d or 3d edition

 ISBN13: 978-1-133-18779-0

Nielsen and Chuang: Quantum Computation and Quantum Information, 2d edition, 2010.

ASSESSMENT

50% exam; 20% test; 30% assignments