Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Computational complexity theory (17.DOM46L)

Native organizations units: No data

Type of studies	Title
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
Interdisciplinary	Yes
ECTS	10

Educational goal:

Obtaining fundamental knowledge in complexity theory. Students involvement in scientific research.

Educational outcome:

Knowledge about fundamental notions and results in complexity theory. Ability to employ these methods in research, based on student`s interests and in cooperation with researchers from the region and abroad.

Course content:

Computational complexity of O-notation. Abstract computational complexity. Classes of computational complexity, classes hierarchy. Open problem in the complexity classes hierarchy, P-NO problem. Complete problems. Probabilistic classes of complexity. Application of complexity theory in cryptology.

Teaching methods:

The presentation of the theoretical part during the lectures is followed by the characteristic examples which contribute to better understanding of the subject content. The students are expected to individually study the additional literature which they discuss with the lecturer at the consultation classes. Through research and study work the student will, on the bases of scientific journals and other relevant literature that has been studied independently, develop further understanding of the material covered in lectures. Working with the course lecturer the student develops the ability to independently work on a scientific paper.

Literature:

Authors	Title	Year	Publisher	Language
C. Papadimitriou	Computational complexity	1995	Addison-Wesley	English
H. Lewis, C. Papadimitriou	Elements of the theory of computation	1981	Prentice-Hall	English
Zoran Ognjanović, Nenad Krdžavac	Uvod u teorijsko računarstvo	2005	Fakultet organizacionih nauka, Beograd	Serbian language
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	English