Реєстраційний номер
0507U000195, Докторська дисертація
На здобуття
д.ф.-м.н.
Дата захисту
19-03-2007
Статус
Захищена
Назва роботи
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дь на вiдкрите питання Крайчика та Пудлака про iснування оптимальних алгоритмiв для coNP-задач.
Дата реєстрації
2007-04-11
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-30