## Abstract

The objective of this course is to use the formal algorithmic system provided by Turing machines as a tool to analyze the complexity of decision and optimization problems and the algorithms that solve them. The topics to be covered include

• the definition of the time and space complexity of a deterministic algorithm

• the classes of deterministic polynomial and non-polynomial time languages

• the complexity of nondeterministic algorithms

• the P=NP question (relationship between solvability by deterministic and nondeterministic polynomial time algorithms)

• the implications of a solution to the P=NP question

• NP completeness and examples of NP complete problems

• classes of NP complete problems

• techniques for approximate solutions of NP complete problems

Original language | American English |
---|---|

State | Published - Apr 1 2008 |

## Disciplines

- Computer Engineering
- Computer Sciences
- Engineering
- Physical Sciences and Mathematics