• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Математические методы в теории сложности вычислений и алгоритмической теории игр

Приоритетные направления развития: компьютерно-математическое, математика
2020

Выполенные работы

Изучалась задача о ширине закрашиваний правильных скобочных выражений.

Исследовалась задача о решении многомерных игр вычитания.

Изучались базовые меры сложности булевых функций, такие как степень (над полем действительных чисел), блочная чувствительность, сложность в модели разрешающих деревьев.

Рассматривалась сюръективная задача удовлетворения ограничениям и ее сложность.

Рассматривались так называемые последовательные реагирующие онлайн-системы, работающие с бесконечными потоками входных и выходных сигналов и наделённые лишь конечным объёмом памяти.

Исследовались свойства грамматик, разбирающих выражение.

В области теории игр исследовались свойства игры точный медленный НИМ.

Рассматривались апериодические замощения плоскости прямоугольными треугольниками.

Рассматривалось вычисление булевой функции голосования схемами, состоящими из функций голосования от меньшего числа переменных.

Используемые методы

В работе по проекту использовался широкий спектр математических методов и методов теоретической информатики, включая комбинаторные, вероятностные, алгебраические методы, а также методы математической логики и теории алгоритмов.

Эмпирическая база исследования

Работа по проекту носит теоретический характер и не требует эмпирической базы.

Результаты работы

Найдены новые нижние оценки в задаче о ширине закрашиваний правильных скобочных выражений и получены приложения этих оценок к анализу сложности в теории формальных языков.

Доказано, что задача о решении многомерных игр вычитания является EXP-трудной даже для случая ограниченной размерности игры.

Для сложности булевых функций был усилена известная нижняя оценка на ее степень через блочную чувствительность.

Была доказана сильная нижняя оценка сложности булевой функции голосования в модели разрешающих деревьев с запросами, зависящими от двух переменных.

Был построен пример языка ограничений, для которого сюръективная задача удовлетворения ограничениям полиномиально разрешима, тогда как общая задача удовлетворения ограничениям NP-полна.

В исследованиях по последовательным реагирующим системам рассматривались расширенная логика {LP}-CTL* и её регулярный фрагмент Reg-CTL*. Для этого фрагмента был разработан алгоритм верификации.

Для грамматик, разбирающих выражение, было показано, что класс языков, задаваемых такими грамматиками, содержит регулярное замыкание детерминированных КС-языков.

Для игры точный медленный НИМ было найдено явное выражение функции Шпрага-Гранди для большого числа различных значений параметров.

Для апериодических замощений плоскости прямоугольными треугольниками было доказано, что можно добавить цвета на плитки так, чтобы для цветных плиток можно было задать семейство апериодических замощений локальными правилами.

Для различных значений параметров было построено семейство схем, состоящих из функций голосования небольшого числа переменных, небольшой глубины, вычисляющих функцию голосования от n переменных.

Публикации по проекту:


Vereshchagin N. Descriptive complexity of computable sequences revisited // Theoretical Computer Science. 2020. Vol. 809. P. 531-537. doi
Durand B., Shen A., Vereshchagin N. On the Structure of Ammann A2 Tilings // Discrete and Computational Geometry. 2020. Vol. 63. P. 577-606. doi
Boros E., Gurvich V., Milanic M. Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1‐Sperner hypergraphs // Journal of Graph Theory. 2020. Vol. 94. No. 3. P. 364-397. doi
Boros E., Gurvich V., Bao Ho Nhan, Makino K. On the Sprague–Grundy function of extensions of proper NIM // International Journal of Game Theory. 2020. doi
Podolskii V. V., Sherstov A. A. Inner Product and Set Disjointness: Beyond Logarithmically Many Parties // ACM Transactions on Computation Theory. 2020. Vol. 12. No. 4. P. 26-. doi
Grigoriev D., Podolskii V. V. Tropical Combinatorial Nullstellensatz and Sparse Polynomials // Foundations of Computational Mathematics. 2020. Vol. 20. No. 4. P. 753-781. doi
Chistikov D., Mikhail V. Re-pairing brackets, in: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020.: Association for Computing Machinery (ACM), 2020. С. 312-326. 
Gurvich V., Vyalyi M. Computational hardness of multidimensional subtraction games, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings.: Springer, 2020. С. 237-249. 
Chistopolskaya A., Podolskii V. V. On the Decision Tree Complexity of Threshold Functions, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings.: Springer, 2020. С. 198-210. 
Vereshchagin N. A family of non-periodic tilings of the plane by right golden triangles / Cornell University. Series math "arxiv.org". "arXiv:2007.10658". 2020.