Вербіцький О. В. Iгровi та екстремальнi задачi комбiнаторики iз застосуваннями в теорiї складностi

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