Пошук академічних текстів

Інформація × Реєстраційний номер 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-03-19 Додано в НРАТ 2020-04-04 Закрити