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 oaf 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