Description
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
<a href="https://corescholar.libraries.wright.edu/cgi/viewcontent.cgi?article=1756&context=cecs_syllabi">Course Syllabi</a>