Эффективные представления стандартных математических структур

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

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

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 23-11-00170

НазваниеЭффективные представления стандартных математических структур

Руководитель Гончаров Сергей Савостьянович, Доктор физико-математических наук

Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Новосибирский национальный исследовательский государственный университет" , Новосибирская обл

Конкурс №80 - Конкурс 2023 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-101 - Математическая логика и основания математики

Ключевые слова вычислимость, полиномиальная вычислимость, примитивно рекурсивная вычислимость, автоматы, структура, модели теории, поля, кольца, группы, метрические пространства, топологические пространства, векторные пространства, булевы алгебры, нормированные пространства, семантическое программирование

Код ГРНТИ27.03.45

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Исторически математические структуры (группы, кольца, поля, векторные, метрические и топологические пространства, проективные плоскости и т.д.) возникали как абстрактные обобщения различных математических объектов, на которых заданы определённые операции, отношения и связи различного вида. Развитие компьютерной техники и вычислительных технологий сделало актуальной задачу искать или строить эффективные представление этих абстрактных объектов, которые позволяют применять алгоритмы для решения связанных с ними задач. Общая задача проекта - построение и изучение таких эффективных представлений для ряда важных математических структур, исследование вопроса о том, как связаны различные представления друг с другом и насколько разными они могут быть. В частности, в ходе работы над проектом будут изучены соотношения различных типов вычислимости применительно к математическим структурам: связь классической вычислимости, примитивно рекурсивной вычислимости, вычислимости за ограниченное (полиномиальное) время, вычислимости на BSS-машинах и вычислимости с арифметическим оракулом. Поиск новых эффективных представлений для абстрактных математических объектов позволяет применять к ним теорию вычислимости, теорию сложности вычислений и в итоге находить алгоритмические решения тех или иных задач, а также доказывать, что таких решений, вообще говоря, не существует. Даже если полученные алгоритмы на практике оказываются недостаточно быстрыми, сам факт их существования (или отсутствия таких алгоритмов) является важным этапом изучения общих математических структур, позволяющим планировать будущие исследования. Связь различных типов вычислимости друг с другом позволяет в некоторых случаях сводить одни задачи к другим. Алгебраическая структура (т.е. множество с операциями и предикатами) называется вычислимой за полиномиальное время (коротко, P-вычислимой), если её элементы можно закодировать словами конечного алфавита так, чтобы операции и предикаты можно было задать алгоритмами, вычислимыми за полиномиальное время. Одна из базовых задач проекта - исследование вопроса о том, когда у данной структуры есть изоморфное представление, вычислимое за полиномиальное время. В рамках работы над проектом планируется найти общий критерий того, что у данной структуры есть такое представление. Планируется также решить серию вопросов о существовании вычислимых и примитивно рекурсивных представлений. Изучая классы моделей теорий, мы можем гарантировать наличие моделей с заданными алгоритмическими свойствами. В рамках данного проекта предполагается изучение вычислимых моделей эренфойхтовых теорий, то есть теорий с конечным (с точностью до изоморфизма) числом счётных моделей. В более широком смысле математические структуры включают в себя не только структуры алгебраического типа, но также метрические, нормированные и топологические пространства. Для них также существуют естественные подходы к определению таких понятий, как вычислимое или примитивно рекурсивное пространство. Планируется, что будет исследован ряд вопросов, связанных с такими пространствами. Планируется перенос на вычислимые польские пространства ряда теорем классической теории вычислимости или доказательство невозможности такого переноса. Естественным расширением понятия вычислимой структуры является понятие структуры, представимой с помощью BSS-машин, работающих в бесконечном времени (сокращённо ITBM). В ходе работы над проектом предполагается изучение вопросов существования ITBM-представлений для широкого класса континуальных алгебраических структур. Ещё одним направлением работы в рамках данного проекта станет изучение систем уравнений и координатных алгебр над алгебраическими структурами. Также будет изучаться алгоритмическая сложность проблемы существования хорнова представления формул в различных классических элементарных теориях.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Алаев П.Е. Критерий P-вычислимости структур Алгебра и логика, т. 61, №5, с. 640-646 (год публикации - 2023)
10.33048/alglog.2022.61.507

2. Коровина М.В., Кудинов О.В. Порядково позитивные поля Алгебра и логика, т.62 (год публикации - 2024)

3. Павел Алаев Inversion in P-Computable Fields Lecture Notes in Computer Science, т. 14773, с. 100-109 (год публикации - 2024)

4. С.С.Гончаров Computable Boolean algebras and complexity of the Frechet Ideal Journal of Mathematical Sciences, т.284, №1, с.72-82 (год публикации - 2024)
10.1007/s10958-024-07328-1

5. Когабаев Н.Т. The NP-completeness of the consistency problem for systems of Diophantine equations over finite configurations Siberian Mathematical Journal, Vol. 66, No. 3, pp. 702-714 (год публикации - 2025)
10.1134/S0037446625030103

6. Н. Т. Когабаев Complexity of the problem of $\forall$-representation for sentences Algebra and Logic, т. 62, № 4, с. 372-375 (год публикации - 2024)
10.1007/s10469-024-09751-4

7. Гончаров С.С., Сян Ц. Изоморфизм безатомных булевых алгебр с выделенным идеалом Algebra and Logic, Vol. 63, No. 3 (год публикации - 2024)
10.1007/s10469-025-09781-6

8. Коровина М., Кудинов О. Order positive fields II Algebra and Logic, Vol. 64 (год публикации - 2026)

9. Алаев П.Е., Хлестова Е.И. Разрешимые модели эренфойхтовых теорий Algebra and Logic (год публикации - 2024)

10. Гаськова М.Н. The 2-decidability of Boolean algebras with one distinguished ideal Algebra and Logic, Vol. 63, No. 6, pp. 399-409. (год публикации - 2025)
10.1007/s10469-025-09802-4

11. Алаев П.Е. Description of structures computable in polynomial time Annals of Pure and Applied Logic, v.177, 103636 (год публикации - 2025)
10.1016/j.apal.2025.103636

12. Морозов А.С. ITBM-Конструктивные пополнения алгебр Сибирский математический журнал, т. 65 (3), с. 533–544 (год публикации - 2024)
10.33048/smzh.2024.65.308

13. Алаев П.Е. The Existence of Primitive Recursive Structures Lecture Notes in Computer Science, Vol. 15764 (год публикации - 2025)
10.1007/978-3-031-95908-0_9

Аннотация результатов, полученных в 2024 году
Доказано, что любое вычислимое поле характеристики 0, обладающее вычислимо перечислимым базисом трансцендентности, обладает изоморфным P-вычислимым представлением. Было доказано следующее утверждение: если T - эренфойхтова теория с арифметическими типами и у T есть абстрактная предельная модель, в которой выполняется некоторое АЕ-предложение в обогащенной сигнатуре, в которую добавлены предикаты для конечного множества типов, то у Т есть и арифметическая предельная модель, в которой выполняется это предложение. Изучалась сложность проблемы существования $\forall$-предложения ($\exists$-предложения), эквивалентного данному предложению. Доказано, что для сигнатуры, состоящей только из одноместных предикатных символов, обе данные проблемы вычислимы. Если же сигнатура содержит хотя бы два одноместных функциональных символа, установлено, что каждая из указанных проблем является $m$-полным $\Sigma^0_1$-множеством. Доказано, что проблема совместности систем диофантовых уравнений над конечными конфигурациями в проективных плоскостях является NP-полной. Изучалось соотношение между Сигма-представимостью структур в наследственно конечной надстройке над вещественными числами HF(R) и ITBM-вычислимой представимостью структур. Получен общий результат, из которого следует, что любая Сигма-определимая над HF(R) структура ITBM-представима. Обратное утверждение неверно. Исследовались структуры PR(I) и PR(C) fpr-степеней пунктуальных представлений единичного интервала I и пространства Кантора C. Доказано, что PR(C) содержит наибольший элемент, степень стандартного представления C, и состоит из представлений, относительно которых C пунктуально компактно. Все эти представления попарно пунктуально изометричны. PR(I) не имеет наибольшего элемента, но содержит максимальный элемент – степень стандартного представления I. Эта степень состоит из представлений, относительно которых I пунктуально компактно, и все такие представления попарно пунктуально изометричны. Доказано, что вещественное замыкание порядково позитивного поле - снова порядково позитивное поле. Подсчитаны индексные множества следующих классов порядково позитивных полей: (1) архимедовых; (2) архимедовых полей, обладающих вычислимым представлением (конструктивизацией); (3) архимедовых вещественно замкнутых полей; (4) архимедовых регулярно r-замкнутых полей; (5) архимедовых гильбертовых полей. Было доказано, что булева алгебра обладает вычислимым представлением с вычислимым множеством атомов тогда и только тогда, когда она обладает вычислимым представлением, в котором идеал Фреше является вычислимо перечислимым. Было доказано, что существует позитивная атомная булева алгебра, у которой нет вычислимого представления. Доказано, что существует вычислимая булева алгебра с вычислимым множеством атомов такая, что её фактор-алгебра по идеалу Фреше является атомной и не имеет вычислимого представления. Доказано существование вычислимой булевой алгебры A, такой, что (A, At, Als) — вычислимая структура, но у неё нет вычислимого представления B такого, чтобы структура (B, At, Als, Atm) тоже была вычислима. Доказано существование вычислимой булевой алгебры A, такой, что (A, At, Als, Atm) — вычислимая структура, но у неё нет вычислимого представления B такого, чтобы структура (B, At, Als, Atm, E_1) тоже была вычислима.

Публикации

2. Коровина М.В., Кудинов О.В. Порядково позитивные поля Алгебра и логика, т.62 (год публикации - 2024)

3. Павел Алаев Inversion in P-Computable Fields Lecture Notes in Computer Science, т. 14773, с. 100-109 (год публикации - 2024)

8. Коровина М., Кудинов О. Order positive fields II Algebra and Logic, Vol. 64 (год публикации - 2026)

9. Алаев П.Е., Хлестова Е.И. Разрешимые модели эренфойхтовых теорий Algebra and Logic (год публикации - 2024)

11. Алаев П.Е. Description of structures computable in polynomial time Annals of Pure and Applied Logic, v.177, 103636 (год публикации - 2025)
10.1016/j.apal.2025.103636

13. Алаев П.Е. The Existence of Primitive Recursive Structures Lecture Notes in Computer Science, Vol. 15764 (год публикации - 2025)
10.1007/978-3-031-95908-0_9