Download Full Text (2.2 MB)
I will discuss the basic notions related to the complexity theory. The classes of P and NP problems will be defined, with examples given. Besides discussing the statements of the problems, I will talk about the effectiveness of algorithms used in linear algebra (multiplying matrices and solving the systems of linear equations). No previous knowledge of complexity theory will be assumed, however some knowledge of linear algebra (matrices and their multiplication) will be needed.
Applied Mathematics | Mathematics
Weyman, Jerzy, "Algebraic Complexity Theory" (2015). Dalrymple Lecture Series. 3.