University of Passau - Code: 482211;
Lecturer: Müller;
Course content:
Computational complexity theory aims to classify computational problems according to the algorithmic resources
required for their solution. Resources are for example time, space, nondeterminism, or randomness. A central role
is played by the class P of problems solvable in polynomial time. The central problem is the P versus NP problem,
one of the Clay institute's millenium problems of mathematics, and, according to Smale, one of the three greatest
open problems of mathematics.
Poslední úprava: Holubová Irena, doc. RNDr., Ph.D. (06.03.2025)
Literatura - angličtina
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.;
