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