Official government website of the Government of the Kingdom of Saudi ArabiaHow is it achieved?

The Saudi official educational websites' links end with edu.sa

Check the domain's scope in the browser's address bar before sharing your data.

Trusted government websites use a protocol HTTPS

Check that the site uses HTTPS protocol to encrypt the connection.

Digital Government Authority Registered with the Digital Government Authority with no: 20260416249

What are you looking for?

Colleges

Computational complexity

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.

Additional information:

Last update date of the page content:

survey_v2

Cookies

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