• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Mathematical methods in algorithm theory and computational complexity

Priority areas of development: mathematics
2019
The project has been carried out as part of the HSE Program of Fundamental Studies.

Цель работы

Изучались свойства сумм Минковского над булевым кубом.

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

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

Исследовались свойства так называемых 1-Шпернеровых гиперграфов.

Исследовались игры двух лиц с нулевой суммой, полной информацией и предельным средним эффективным платежом.

Исследовались игры НИМ на гиперграфах и задача определения победителя в них.

Исследовалось понятие автоматной размерности, впервые введенной Даи, Латропом, Лутцем и Майордомо.

Исследовалась задача подсчета числа корней разреженного многочлена над конечным полем и ее алгоритмическая сложность.

Исследовалась связь между дефектом случайности и дефектом оптимальности для колмогоровской сложности с ограничением на память.

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

Исследовалось вычисление булевых линейных операторов над произвольными полугруппами.

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

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

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

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

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

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

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

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

Доказано, что задача распознавания сепарабельности частично определенных функций n переменных является NP-полной для n > 2. Из этого результата вытекает, что задача разпознования сепарабельности полностью определённых дискретных функций n переменных NP-полна при n > 3.

Получена каноническая декомпозиция так называемых 1-Шпернеровых гиперграфов.

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

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

Предъявлены два новых эквивалентных определения автоматной размерности, впервые введенной Даи, Латропом, Лутцем и Майордомо.

Доказано, что задача подсчета числа корней разреженного многочлена над конечным полем является #P-полной относительно детерминированого сведения.

Была установлена связь между дефектом случайности и дефектом оптимальности для колмогоровской сложности с ограничением на память.

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

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

Доказано, что если n=8k+2, где k — любое натуральное число, то сложность пороговой функции от n переменных с порогом 3 в модели разрешающих деревьев с XOR запросами равна n-1.

Publications:


Podolskii V. V., Kulikov A. S. Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates // Theory of Computing Systems. 2019. Vol. 63. No. 5. P. 956-986. doi
Milovanov A. On Algorithmic Statistics for Space-bounded Algorithms // Theory of Computing Systems. 2019. Vol. 63. No. 4. P. 833-848. 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
Buhrman H., Torenvliet L., Unger F., Vereshchagin N. Sparse Selfreducible Sets and Nonuniform Lower Bounds // Algorithmica. 2019. Vol. 81. No. 1. P. 179-200. doi
Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Sprague-Grundy function of matroids and related hypergraphs // Theoretical Computer Science. 2019. Vol. 799. P. 40-59. doi
Boros E., Elbassioni K. M., Gurvich V., Makino K. A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions // Information and Computation. 2019. Vol. 267. P. 74-95. doi
Boros E., Gurvich V., Milanic M. Decomposing 1-Sperner Hypergraphs // Electronic Journal of Combinatorics. 2019. Vol. 26. No. 3
Vyalyi M., Леонтьев В. К. Geometry of Translations on a Boolean Cube / Пер. с рус. // Problems of Information Transmission. 2019. Vol. 55. No. 2. P. 152-173. doi
Boros E., Cepek O., Gurvich V. Separable discrete functions: Recognition and sufficient conditions // Discrete Mathematics. 2019. Vol. 342. No. 5. P. 1275-1292. doi
Rubtsov A. A., Vyalyi M. On Computational Complexity of Set Automata // Information and Computation. 2019
Rubtsov A. A. Framework for Formal Languages, in: Proceedings of Language and Automata Theory and Applications 2020. Springer, 2020.
Milovanov A. #P-completeness of counting roots of a sparse polynomial // Information Processing Letters. 2019. Vol. 142. P. 77-79. doi
Boros E., Gurvich V., Bao Ho N., Makino K., Mursic P. Sprague–Grundy function of symmetric hypergraphs // Journal of Combinatorial Theory, Series A. 2019. Vol. 165. No. 7. P. 176-186. doi