The course describes: Introduction to computational complexity theory. Topics include easy and hard problems, Turing machines, the halting problem and nondeterministic languages (the universal Turing machine), categories of necessary complexity, P and NP, and completeness-NP (non-universal Turing machines, the Hamilton path, quasi-bounded time, NP-hardness). In addition, the course covers topics related to optimization and approximation, with advanced concepts presented to students such as randomized complexity.
Credit hours: 3
Objectives of the course :
• Categorizing the issues of the resolution into appropriate complexity levels.
• Expressing precisely what it means to reduce an issue to another, and constructing reduction processes for simple examples.
• Categorizing improvement issues into appropriate approximation complexity categories and effectively using this information.
Course outputs :
1. Knowledge and understanding:
1.1. Categorizing the issues of the resolution into appropriate complexity categories.
1.2. Expressing precisely what it means to reduce a problem to another, and constructing reduction processes for simple examples.
2. Skills:
2.1. Design solutions for specific improvement issues.
2.2. Using the concept of interactive proofs in analyzing improvement issues.
3. Values:
3.1. The ability to apply interactive arguments in the analysis of improvement issues.
This website uses special cookies to ensure ease of use, improve your browsing experience, and clarify the terms and policies related to About user privacy. By continuing to browse this website, you acknowledge that you accept the use of cookies and the terms of the Privacy Policy