| Course code | CSCI5170 |
| Course title | Theory of Computational Complexity 計算複雜性理論 |
| Course description | This course introduces some of the following topics: deterministic and non-deterministic Turing machine, time and space complexity, NP-completeness, polynomial time hierarchy, probabilistic computation, interactive proofs, complexity of counting, concrete models such as query complexity, communication complexity, formula complexity, branching programs and circuit complexity, quantum computation, complexity-based cryptography, randomness-related topics such as derandomness, pseudorandomness, extractors, random walks, etc. 本科將從如下內容中選擇介紹：確定性和不確定性圖靈機，時間和空間複雜性，NP完全性，多項式時間等級，交互證明，計數複雜性，具體模型如查詢複雜性，通信複雜性，公式复杂性，分支程序，電路複雜性，量子計算，基於複雜性的密碼學，隨機性相關課題如消隨機，偽隨機，抽取器，隨機遊走等。 |
| Unit(s) | 3 |
| Course level | Postgraduate |
| Semester | 1 or 2 |
| Grading basis | Graded |
| Grade Descriptors | A/A-: EXCELLENT – exceptionally good performance and far exceeding expectation in all or most of the course learning outcomes; demonstration of superior understanding of the subject matter, the ability to analyze problems and apply extensive knowledge, and skillful use of concepts and materials to derive proper solutions. B+/B/B-: GOOD – good performance in all course learning outcomes and exceeding expectation in some of them; demonstration of good understanding of the subject matter and the ability to use proper concepts and materials to solve most of the problems encountered. C+/C/C-: FAIR – adequate performance and meeting expectation in all course learning outcomes; demonstration of adequate understanding of the subject matter and the ability to solve simple problems. D+/D: MARGINAL – performance barely meets the expectation in the essential course learning outcomes; demonstration of partial understanding of the subject matter and the ability to solve simple problems. F: FAILURE – performance does not meet the expectation in the essential course learning outcomes; demonstration of serious deficiencies and the need to retake the course. |
| Learning outcomes | At the end of the course of studies, students will have acquired the ability to 1. understand the typical complexity classes and common techniques for various reductions; 2. prove lower bounds in concrete complexity models. |
| Assessment (for reference only) |
|
| Recommended Reading List | 1. Computational Complexity—A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009. 2. Computational Complexity: A Conceptual Perspective, Oded Goldreich, Cambridge University Press, 2008. 3. Boolean Function Complexity: Advances and Frontiers, Stasys Jukna, Springer, 2012. |
| CSCIN programme learning outcomes | Course mapping |
| Upon completion of their studies, students will be able to: | |
| 1. identify, formulate, and solve computer science problems (K/S); | |
| 2. design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs (K/S); |
|
| 3. receive the broad education necessary to understand the impact of computer science solutions in a global and societal context (K/V); | TP |
| 4. communicate effectively (S/V); |
TP |
| 5. succeed in research or industry related to computer science (K/S/V); |
TP |
| 6. have solid knowledge in computer science and engineering, including programming and languages, algorithms, theory, databases, etc. (K/S); | T |
| 7. integrate well into and contribute to the local society and the global community related to computer science (K/S/V); | |
| 8. practise high standard of professional ethics (V); | |
| 9. draw on and integrate knowledge from many related areas (K/S/V); |
TP |
| Remarks: K = Knowledge outcomes; S = Skills outcomes; V = Values and attitude outcomes; T = Teach; P = Practice; M = Measured | |