- About Us
- About University
- Double degree programmes
- Learning Page
- Courses
- Faculty of Computer Science and Cybernetics
- Faculty of Economics
- Faculty of Geography
- Faculty of History
- Faculty of Information Technology
- Faculty of Law
- Faculty of Mechanics and Mathematics
- Faculty of Physics
- Faculty of Psychology
- Faculty of Sociology
- Institute of Geology
- Institute of High Technologies
- Institute of International Relations
- Institute of Journalism
- Institute of Philology
- Military Institute
- Philosophical Faculty

- Regulations
- Contacts

# 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 |