| CS4995: | Introduction to |
| Computational Complexity(CVN) | |
| Fall 2005 |
Many computational problems (such as multiplying two numbers, or sorting a list of numbers) are known to be "easy" in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great practical importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult, in the sense that no efficient algorithms are known. Are these problems really inherently difficult -- do no efficient algorithms exist? -- or do we just need to come up with cleverer algorithms that can solve these problems efficiently?
Questions such as these lie at the heart of computational complexity, which is the study of the fundamental abilities and limitations of efficient computation. Over the past few decades, computational complexity has emerged as one of the most dynamic, interesting and important areas in computer science; indeed, the core question of computational complexity theory ("does P equal NP?") is now widely viewed as one of the most famous and important open questions in all of computer science and mathematics.
Computational complexity has given us more than just questions, though; it has made fundamental contributions to our understanding of many central ideas and topics in computer science. To give a few examples, our understanding of many interesting and practically important optimization problems was revolutionized by the theory of NP-completeness several decades ago. More recently, the use of randomness as a tool for designing efficient algorithms was pioneered in computational complexity. Even the notion of what it means to prove that a statement is true has undergone a revolution as a consequence of interactive proofs and probabilistically checkable proofs (PCPs) in complexity theory! We'll study all these topics, and more, in this class.
This is a preliminary list; we may cover more or less material depending on how the semester progresses.
The prerequisite for this course is an introductory course on theory of computation, i.e. W3261 (or the equivalent at another university), with a good grade (B+ or higher). If you do not formally meet this requirement but still wish to take this course, you must come to my office hours to discuss your background. A prior course in algorithms such as W3139 or W4231 is also helpful but is not required.
The most important topics that we will be assuming comfort with are Turing machines, basic notions of computability, and asymptotics (big-O notation and the like). Roughly speaking, you should be comfortable with the first five chapters of Sipser's book (see below), and ideally you will have had some exposure to the material in Chapter 7. Prior acquaintance with P, NP-completeness and the like is helpful but not required. General mathematical maturity, e.g. comfort with proofs, basic discrete probability, & combinatorics will be assumed.