Вербіцький О.В. Ігрові та екстремальні задачі комбінаторики із застосуваннями в теорії складності. - Рукопис. Дисертація на здобуття наукового ступеня доктора фізико-матема-тичних наук за спеціальністю 01.01.08 - математична логіка, теорія алгоритмів та дискретна математика. - Київський національний університет імені Тараса Шевченка, Київ, 2007. Дисертація присвячена задачам комбінаторної теорії ігор та екстремальної комбінаторики, причому особлива увага приділена питанням конструктивності та застосуванням в теорії складності обчислень та теорії дескриптивної складності. Розв'язано ряд екстремальних задач Рамсеївського типу для симетричних підмножин Евклідового простору, причому значення екстремальних функцій досягаються ефективними детермінованими або ймовірнісними конструкціями. Для класу сильних ігор на уникнення забороненого підграфа введено і вивчено поняття симетричної стратегії. Введено поняття логічної глибини графа і отримано оцінки цього інваріанту на основі всебічного вивчення гри Еренфойхта на графах. Ці оцінки застосовано для аналізу алгоритму Вайсфайлера-Лемана розпізнавання ізоморфних графів. Шляхом ігрової інтерпретації та зведенням до екстремальних задач отримано результати про паралельне повторення інтерактивних доведень. Розроблено доведення без розголошення для теоретико-групових задач про перестановки. Встановлено обчислювальну важкість форсингово-го хроматичного числа графа. Проведено оракульну конструкцію, яка дає відповідь на відкрите питання Крайчика та Пудлака про існування оптимальних алгоритмів для coNP-задач. Ключові слова: комбінаторні ігри, екстремальна комбінаторика, обчислювальна складність, дескриптивна складність, теорія Рамсея, гра Еренфойхта, закон нуля та одиниці для логіки першого порядку, доведення без розголошення, форсингове хроматичне число.