1

complexity theory

Descipline complexity theory
Faculty Faculty of Mechanics and Mathematics
Faculty URL http://www.mechmat.univ.kiev.ua/en
Language English
Degree Bachelor
Credits 3
Semester 6
Description Computing tasks and model. The tasks of search and recognition. Determination nondetermination, orakular and probability Turing machine. Algorithmic undecidable problem. Boolean circuit.
The main classes of complexity.
Temporal and spatial complexity. The classes P and NP. Composite polynomial. The class PSPACE. Interactive proof. NP-completeness.
Cook-Levin theorem. NP-complete problems in mathematical logic, graph theory and number theory. The use of cryptography.
Teachers Olijnyk A.S.
Department of algebra and mathematical logic,
Faculty of Mechanics and Mathematics,
Phone:
+380442590517
e-mail: aolijnyk@gmail.com
Author: admin