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