Math 170:
Computational Complexity
TuTh 12:45–2:00p.m.
Monroe
Hall B31
Valentina
Harizanov
Monroe Hall, Room 240
Tel:
(202) 994–6235, Fax: (202) 994–6760
Valentina Harizanov
Office: Goverment Hall, Room 220
Tel: (202) 994–6595
E-mail: harizanv@gwu.edu
Web page: http://home.gwu.edu/~harizanv/
Tu 2:05–3:05 p.m.
Th 11:40a.m.–12:40 p.m.
At other times by appointment.
- Description.
By devising a conceptual machine that carried out algorithms, British
logician Alan Turing captured the essence of the intuitive notion of
computability. Since this and early achievements of logic in formalizing
the concept of an algorithm, the theory of computation has developed into
a broad and rich discipline. The study of time and space complexity
measures of algorithms has relatively recently resulted into an important
area of research known as complexity theory. At present a fascinating new
theory of quantum computation and its complexity has been emerging.
Quantum computers should be exponentially faster than the classical ones.
A race to build a quantum computer is on, but the mathematical and other
scientific challenges are enormous.
- Topics.
Finite automata. Pushdown automata. Turing machines. Deterministic and
nondeterministic space and time complexity classes. Relations among
complexity measure. Intractable problems. Polynomial-time reducibility and
NP-completeness. Various NP-complete problems: the satisfiability
problem, the vertex cover problem, the traveling salesman problem. Quantum
computation and its mathematical model. Quantum algorithms and their
complexity classes.
- Required
background. Math 32 or permission of instructor. This course can be
taken for undergraduate or graduate credit. Graduate credit students will
have more advanced assignments.
- Grading.
Take-home assignments (60%), midterm exam (20%), take-home
final project (20%).
- Textbook.
Introduction to the Theory of Computation by Michael Sipser, PWS Publishing Company.
Reading material on quantum
computation and its complexity will be provided in class.