Undergraduate Course: Computational Complexity (INFR10008)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Course type  Standard 
Availability  Available to all students 
Credit level (Normal year taken)  SCQF Level 10 (Year 4 Undergraduate) 
Credits  10 
Home subject area  Informatics 
Other subject area  None 
Course website 
http://course.inf.ed.ac.uk/cmc 
Taught in Gaelic?  No 
Course description  The module extends a line of study, begun in CS3 Computability and Intractability, in which computational problems are classified 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 nondeterminism. 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 nonapproximability of combinatorial optimisation problems. Finally, we investigate some really hard problems that are provably intractable. 
Entry Requirements (not applicable to Visiting Students)
Prerequisites 

Corequisites  
Prohibited Combinations  
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. 
Additional Costs  None 
Information for Visiting Students
Prerequisites  None 
Displayed in Visiting Students Prospectus?  Yes 
Course Delivery Information

Delivery period: 2013/14 Semester 2, Available to all students (SV1)

Learn enabled: No 
Quota: None 

Web Timetable 
Web Timetable 
Course Start Date 
13/01/2014 
Breakdown of 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 )

Additional Notes 

Breakdown of Assessment Methods (Further Info) 
Written Exam
75 %,
Coursework
25 %,
Practical Exam
0 %

Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S2 (April/May)   2:00  
Summary of Intended Learning Outcomes
1  Students will be able to formulate models of sequential, randomised and parallel compution, 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). 
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0
Assessment
Three collections of pencilandpaper exercises issued at approximately threeweek intervals.
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. 
Special Arrangements
None 
Additional Information
Academic description 
Not entered 
Syllabus 
* 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 nonuniform 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 
Transferable skills 
Not entered 
Reading list 
* Papadimitriou, 'Computational Complexity', AddisonWesley 1994.
* Garey and Johnson, 'Computers and IntractabilityA Guide to the Theory of NPCompleteness', 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

Study Abroad 
Not entered 
Study Pattern 
Lectures 20
Tutorials 0
Timetabled Laboratories 0
Nontimetabled assessed assignments 25
Private Study/Other 55
Total 100 
Keywords  Not entered 
Contacts
Course organiser  Dr Mary Cryan
Tel: (0131 6)50 5153
Email: mcryan@inf.ed.ac.uk 
Course secretary  Miss Kate Farrow
Tel: (0131 6)50 2706
Email: Kate.Farrow@ed.ac.uk 

