Арбузная корка академика Гончарова С.С.

В конце 2022 года в Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук (Новосибирск) была защищена, под научным руководством академика РАН, профессора, доктора наук Гончарова С.С. и в соавторстве с ним, диссертация «Полиномиальная вычислимость в семантическом программировании».

Замах на решение проблемы «P=L» и языка L: анализ р-полноты

 

Главным, центральным результатом диссертации является, в формулировке авторов, «решение проблемы P=L», а на самом деле построение языка L и доказательство его р-полноты. 

Приведённая авторами диссертации формулировка не имеет отношения к знаменитой проблеме равенства классов сложности P и NP, у них «P=L» означает доказательство того, что класс полиномиально вычислимых функций (P) совпадает с классом функций, вычислимых на языке L. Иными словами, доказывается, что если язык L является р-полным, то любая программа на языке L вычисляется за полиномиальное время, и любая полиномиально вычислимая функция может быть реализована на языке L.

Для достижения р-полноты авторы вводят синтаксическую конструкцию — «р-итерационный терм» (p-iterational term).

Приведённое авторами доказательство того, что эта конструкция обеспечивает р-полноту (Теорема 1.4, «Решение проблемы P=L») носит явно утилитарный характер, поскольку вычисление авторами р-итерационного терма в точности воспроизводит вычисление на машине Тьюринга.

Всё доказательство сводится к тому, что язык L, оснащенный р-итерационным термом, способен реализовать любую такую функцию, поскольку любая полиномиально вычислимая функция по определению вычисляется некоторой полиномиальной машиной Тьюринга.

Приведённое авторами диссертации доказательство по своей сути является утилитарным, поскольку p-итерационный терм не описывает свойства, которым должен удовлетворять результат вычисления (как это делают, например, логики с неподвижной точкой, Immerman, Neil (1999). Descriptive complexity; Immerman, Neil (1986). «Relational queries computable in polynomial time». Information and Control; Vardi, Moshe Y. (1982). «The complexity of relational query languages (Extended Abstract)». Proceedings of the fourteenth annual ACM symposium on Theory of computing), а всего лишь предписывает простую процедуру его получения путём обычной имитации общеизвестного вычислительного механизма Тьюринга.

В чём же новизна вышеуказанного результата авторов диссертации? Уж конечно не в открытии того факта, что ограниченная итерация позволяет достичь полиномиальной полноты, просто в силу того, что этот факт общеизвестен научной общественности. Если же за научную новизну считать интеграцию этого незамысловатого утилитарного механизма в декларативную по своей природе парадигму семантического программирования, ну что ж …  В таком случае предполагаем, что представление авторов диссертации о научной новизне вряд ли совпадает с мнением научного сообщества о том, что такое научная новизна …

 

Сравнение результатов диссертации с многолетними исследованиями по поиску логического описания класса Р (PTIME) в области дескриптивной сложности, вернее, полное отсутствие проведения такового авторами диссертации

 

Авторы нигде не обсуждает проблему упорядоченных и неупорядоченных структур, которая является центральной для дескриптивной сложности, при этом их базовая модель HW(M) основана на списках, которые являются неявно упорядоченными структурами.

Неявная упорядоченность, заложенная в саму природу предложенной в диссертации модели, позволяет языку L легко моделировать машину Тьюринга, лента которой также является упорядоченной структурой.

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

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

Фундаментальная машинно-независимая характеризация класса PTIME на упорядоченных структурах была осуществлена за 60 (шестьдесят) лет до публикации авторами диссертации своих «открытий».

Вклад теоремы Иммермана-Варди именно и состоит в машинно-независимой фундаментальной характеризации PTIME на упорядоченных структурах.

В то время как вклад диссертации состоит в интеграции ограниченной итерационной конструкции в парадигму семантического программирования.

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

 

Методология диссертации: PAG-теорема и GNF-системы

 

GNF-система в диссертации — это некий формализм, созданной специально для нужд диссертации, который служит для того, чтобы стандартизировать и упростить постановку задач о полиномиальной вычислимости для индуктивно заданных множеств в рамках модели HW(M).

Классическая теорема Ганди — это глубокий результат в теории обобщенной вычислимости, который устанавливает связь между логической определимостью, а именно, Σ1-определимостью, и индуктивной определимостью.

Теорема Ганди характеризует фундаментальный уровень в иерархии вычислимости, это фундаментальный результат о природе вычислимости.

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

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

Отсутствие практической жизнеспособности результатов диссертации

 

Несмотря на формальную корректность доказательства р-вычислимости L∗-программ (Теорема 4.3), при более глубоком анализе возникает серьезный вопрос о практической применимости языка для создания «быстрых и четких» систем, как это заявлено авторами диссертации во введении.

Проблема кроется именно в том, о чем авторы диссертации скромно умалчивают: о степени полинома, ограничивающего время работы.

Теорема 4.3 гарантирует, что для любой L∗-программы существует полином P(n), ограничивающий ее время работы, но ничего не говорит о том, насколько большой может быть степень этого полинома.

Анализ доказательства Леммы 4.2, которая оценивает рост размера данных, дает основания для беспокойства. В доказательстве приводится оценка, которая по своей структуре напоминает перемножение степеней полиномов при вложенных вызовах.

Приведённая там формула показывает, как оценка размера результата v в вызывающей программе p∗∗ зависит от оценки размера результата b в вызываемой подпрограмме q∗. Если грубо оценить сложность, то вызов из программы со сложностью O(na) подпрограммы со сложностью O(mb) (где m — размер входа в подпрограмму, который сам может быть полиномом от n) может привести к итоговой сложности, связанной с O((na)b)=O(na⋅b).

В языке, который поощряет модульность через функции и методы, это может привести к неконтролируемому росту степени полинома.

Программист, собирая программу из готовых модулей (методов классов), может легко, сам того не осознавая, создать программу с теоретической сложностью, например, O(n50).

Такая программа, хотя формально и является «полиномиальной», будет абсолютно непрактичной и неэффективной для любых сколько-нибудь значимых размеров входных данных.

Указанное выше является фундаментальным недостатком с точки зрения практической ценности языка. L∗ предоставляет гарантию завершимости в полиномиальное время, но не дает никакой гарантии эффективности.

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

При этом авторы диссертации не предлагают ни механизмы контроля за степенью полинома, ни методы статического анализа, которые могли бы предупреждать программиста о потенциальном «взрыве сложности».

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

 

Оценка оригинальности диссертации относительно международных исследований

 

PAG-теорема является хотя и полезной техникой доказательства для списочной надстройки HW(M), однако по своей фундаментальности и общности, вернее в силу отсутствия фундаментальности и общности, PAG-теорема даже и близко не может быть поставлена (тем более в один ряд) с классической теоремой Ганди или с теоремой Иммермана-Варди.

Результат «P=L»: создание р-полного языка само по себе не является принципиально новой идеей.

Новизна диссертации заключается в том, как указанная неновая, ране уже решённая задача, решена в рамках специфического формализма семантического программирования с помощью оригинальной конструкции р-итерационного терма. Однако, как было сказано выше, этот результат получен для неявно упорядоченной модели (HW(M)), и в силу указанного обстоятельства не решает главную открытую проблему дескриптивной сложности — поиск логики для PTIME на неупорядоченных структурах.

Полное отсутствие в диссертации ссылок на теорему Иммермана-Варди и обсуждения этого контекста является очень серьезным недостатком и упущением диссертации.

Также слабостью диссертации является ее академическая изоляция.

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

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

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

При этом, практическое расширение L∗, будучи теоретически корректным, вызывает серьезные сомнения в своей реальной эффективности из-за потенциально неконтролируемого роста степени полинома, ограничивающего время выполнения программ. Эта проблема потенциально неконтролируемого роста степени полинома, ограничивающего время выполнения программ, имеющая решающее значение для практического применения, в диссертации полностью проигнорирована.

Подводя неутешительные итоги, ответ на вопрос, является ли рассмотренная диссертация «Полиномиальная вычислимость в семантическом программировании» той арбузной коркой академика Гончарова С.С., мы предлагаем уважаемым читателям определить самостоятельно.  

 

Список литературы

1. Solution of the Problem P = L — MDPI, accessed July 22, 2025, https://www.mdpi.com/2227-7390/10/1/113
2. (PDF) Semantic Programming. — ResearchGate, accessed July 22, 2025, https://www.researchgate.net/publication/221329216_Semantic_Programming
3. A Formalization of Document Models with Semantic Modelling — The bulletin of Irkutsk State University. Series «Mathematics», accessed July 22, 2025, https://mathizv.isu.ru/en/article?id=1290
4. СИБИРСКИЕ ЭЛЕКТРОННЫЕ МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ — Siberian Electronic Mathematical Reports, accessed July 22, 2025, http://semr.math.nsc.ru/v17/p380-394.pdf
5. Is there a logic without induction that captures much of P?, accessed July 22, 2025, https://cstheory.stackexchange.com/questions/869/is-there-a-logic-without-induction-that-captures-much-of-p
6. Basic Descriptive Complexity, accessed July 22, 2025, https://sms.wgtn.ac.nz/foswiki/pub/Events/ALC2011/LectureSlides/Chen_Yijia.pdf
7. Fixed-point logic — Wikipedia, accessed July 22, 2025, https://en.wikipedia.org/wiki/Fixed-point_logic
8. Descriptive complexity theory — Wikipedia, accessed July 22, 2025, https://en.wikipedia.org/wiki/Descriptive_complexity_theory
9. Descriptive Complexity — Manning College of Information & Computer Sciences, accessed July 22, 2025, https://people.cs.umass.edu/~immerman/book/ch0_1_2.pdf
10. P and Descriptive Complexity — Theoretical Computer Science Stack Exchange, accessed July 22, 2025, https://cstheory.stackexchange.com/questions/42358/p-and-descriptive-complexity
11. Datalog — Wikipedia, accessed July 22, 2025, https://en.wikipedia.org/wiki/Datalog
12. Lecture 8: Datalog: Evaluation 8.1 Naive Evaluation and Complexity — cs.wisc.edu, accessed July 22, 2025, https://pages.cs.wisc.edu/~paris/cs784-s17/lectures/lecture8.pdf
13. THE COMPLEXITY OF DATALOG ON LINEAR ORDERS 1. Introduction Datalog is the language of logic programming without function symbols — arXiv, accessed July 22, 2025, https://arxiv.org/pdf/0902.1179
14. Polynomial Analogue of Gandy’s Fixed Point Theorem — MDPI, accessed July 22, 2025, https://www.mdpi.com/2227-7390/9/17/2102
15. Functional Variant of Polynomial Analogue of Gandy’s Fixed Point Theorem — DOAJ, accessed July 22, 2025, https://doaj.org/article/998bf69324fa4ed4a2b9c22ef5ec56f5
16. Functional Variant of Polynomial Analogue of Gandy’s Fixed Point Theorem — MDPI, accessed July 22, 2025, https://www.mdpi.com/2227-7390/12/21/3429
17. Polynomial Analogue of Gandy’s Fixed Point Theorem | Semantic Scholar, accessed July 22, 2025, https://pdfs.semanticscholar.org/15be/1893731c0ed9be2e27ed64ae23e6298b6590.pdf
18. CONCEPTUAL-SEMANTIC FORMULA OF THE COGNITIVE-PRAGMATIC PROGRAM “LAW OF CONSCIENCE” (BASED ON THE BOYS FILM CONSTRUCT), accessed July 22, 2025, https://praxema.tspu.ru/en/archive.html?year=2023&issue=2&article_id=8714