Search academic texts

Information × Registration Number 0507U000195, Doctoral dissertation Status д.ф.-м.н. Date 19-03-2007 popup.evolution o 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гор Володимирович 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-03-19 popup.nrat_date 2020-04-04 Close