# DEGREE REGULATIONS & PROGRAMMES OF STUDY 2014/2015 Archive for reference only THIS PAGE IS OUT OF DATE

 University Homepage DRPS Homepage DRPS Search DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

# Undergraduate Course: Computational Complexity (INFR11102)

 School School of Informatics College College of Science and Engineering Credit level (Normal year taken) SCQF Level 11 (Year 4 Undergraduate) Availability Available to all students SCQF Credits 10 ECTS Credits 5 Summary The module studies the problem of classifying computational problems according to their intrinsic difficulty or "complexity". We formalise the notion of complexity of a problem as the amount of time (or space) required to solve the problem on a simple universal computing device, namely the Turing machine. We study some fundamental features of computation in this model, such as time and space hierarchies, the relationship between time and space, and between determinism and non-determinism. We introduce a number of natural complexity classes, which are essentially independent of the Turing machine model, and characterise these classes by identifying some of their complete (i.e., hardest) problems. We then introduce a computational model based on Boolean circuits that allows us to classify problems according to their parallel complexities; as with sequential computation, we are able to separate those problems that can be solved efficiently on a parallel computer from those that (apparently) cannot. Next, we examine the role of randomisation (allowing occasional incorrect answers) in making apparently intractable problems easier. We meet a surprising characterisation of the class NP in terms of ``probabilistically checkable proofs,'' and make an equally surprising connection between this new view of NP and non-approximability of combinatorial optimisation problems. Finally, we investigate some really hard problems that are provably intractable. Course description * The Turing machine model: time and space as complexity measures. * Complexity classes and hierarchies. * Reductions between problems and completeness. * The classes P, NP, PSPACE, LOG, NLOG; examples of complete problems. * Circuits and non-uniform models of computation; the class NC; efficient parallel algorithms. * Randomised algorithms and randomised complexity classes. * Approximate solutions to hard optimisation problems; performance ratios; bounds on performance ratios using the notion of ``probabilistically checkable proof.'' * Provably intractable problems. Relevant QAA Computing Curriculum Sections: Concurrency and Parallelism, Data Structures and Algorithms, Theoretical Computing
 Pre-requisites Co-requisites Prohibited Combinations Students MUST NOT also be taking Computational Complexity (INFR10008) Other requirements This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser. Participants should have some facility with mathematical modes of reasoning.
 Pre-requisites None
 Academic year 2014/15, Available to all students (SV1) Quota:  None Course Start Semester 2 Timetable Timetable Learning and Teaching activities (Further Info) Total Hours: 100 ( Lecture Hours 20, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 76 ) Assessment (Further Info) Written Exam 75 %, Coursework 25 %, Practical Exam 0 % Additional Information (Assessment) Three collections of pencil-and-paper exercises issued at approximately three-week intervals. You should expect to spend approximately 25 hours on the coursework for this course. If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. Feedback Not entered Exam Information Exam Diet Paper Name Hours & Minutes Main Exam Diet S2 (April/May) 2:00
 1 - Students will be able to formulate models of sequential, randomised and parallel computation, and be able to describe the relationships between these models. 2 - They will be able to quantify the resources employed by these models, such as time, space and circuit size/depth. 3 - Students will be able to analyse computational problems from a complexity perspective, and so locate them within the complexity landscape (a landscape which is much refined from that described in Computability and Intractability). 4 - In particular, they will further develop their skill in conducting a completeness proof, which is in a sense a practical skill. 5 - Students will be able to apply mathematical skills and knowledge from earlier years (e.g., from probability theory and logic) to concrete problems in computational complexity. 6 - Students will study the topic in sufficient depth as to gain an appreciation of some of the challenging issues in computer science today (e.g., P =? NP).
 * Papadimitriou, 'Computational Complexity', Addison-Wesley 1994. * Garey and Johnson, 'Computers and Intractability---A Guide to the Theory of NP-Completeness', Freeman 1979. * Sipser, `Introduction to the Theory of Computation', PWS, 1997. *Computational Complexity: A Modern Appraoch, Arora & Barak, Cambridge Uni Press 2009 *Gems of Theoretical Computer Science, Schoning, Springer Verlag 1998
 Course URL http://course.inf.ed.ac.uk/cmc/ Graduate Attributes and Skills Not entered Keywords Not entered
 Course organiser Dr Ilias Diakonikolas Tel: (0131 6)50 5129 Email: idiakoni@exseed.ed.ac.uk Course secretary Miss Claire Edminson Tel: (0131 6)51 4164 Email: C.Edminson@ed.ac.uk
 Navigation Help & Information Home Introduction Glossary Search DPTs and Courses Regulations Regulations Degree Programmes Introduction Browse DPTs Courses Introduction Humanities and Social Science Science and Engineering Medicine and Veterinary Medicine Other Information Combined Course Timetable Prospectuses Important Information
© Copyright 2014 The University of Edinburgh - 12 January 2015 4:12 am