Registration Number
0507U000195, Doctoral dissertation
Status
д.ф.-м.н.
Date
19-03-2007
popup.evolution
.
Title
Game-theoretic and extremal problems of combinatorics with applications in complexity theory
Author
Verbitsky Oleg Vasyliovych,
popup.head Sushchansky Vitalij Ivanovych
popup.opponent Верещагiн Микола Константинович
popup.opponent Кривий Сергiй Лук'янович
popup.opponent Протасов Iгор Володимирович
popup.rada
Taras Shevchenko Kiev University
Description
Дисертац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-задач.
Registration Date
2007-04-11
popup.nrat_date
2020-04-04 / 2026-06-30