Теоретический барьер для нейросимволических агентов
Современные ИИ-агенты, построенные на нейросимволических принципах, всё чаще используют поисковую инфраструктуру как внешнюю память. Цепочка рассуждений при этом компилируется не в простой набор ключевых слов, а в глубоко вложенные булевы запросы с отрицаниями и ветвлениями. Такие запросы выглядят естественно для программиста, но для классического инвертированного индекса они превращаются в серьёзный вызов.
Недавний препринт Амира Аавани на arXiv (2601.18747, последняя версия от 17 августа 2026) показывает, что дело не в лени разработчиков поисковых движков. Автор формализует язык запросов L_R, представленный в виде ориентированного ациклического графа, и строго доказывает: оценка такого запроса над индексом является P-полной задачей. Иными словами, в общем случае этот процесс вряд ли удастся эффективно распараллелить на множестве ядер — если только классы P и NC не окажутся равными, что большинство теоретиков считает крайне маловероятным.
Работа относится сразу к нескольким областям — информационному поиску, искусственному интеллекту, теории сложности, обработке естественного языка и базам данных. Это не случайно: проблема лежит на стыке ИИ и классических поисковых технологий.
Два традиционных подхода и их слабости
Когда запрос выполняется над инвертированным индексом, обычно используют одну из двух стратегий: итеративную обработку по документам (Document-at-a-Time) или материализацию промежуточных списков по термам (Term-at-a-Time). У каждой из них есть свой «скелет в шкафу».
Document-at-a-Time опирается на итераторы с состоянием, которые продвигаются по отсортированным спискам документов. Оказывается, такие итераторы структурно ограничены классом схем NC¹. Если в логике запроса встречаются реконвергентные ветви — то есть несколько путей графа сходятся к одному узлу, — наивное разворачивание этих ветвей в дерево приводит к экспоненциальному взрыву: сложность в худшем случае достигает O(2^{|Q|}), где |Q| — размер запроса.
Term-at-a-Time пытается решить проблему иначе: каждый узел запроса материализуется в виде списка документов. Но для вычисления логического отрицания такой подход вынужден знать весь универсум документов |U|, чтобы понять, какие документы в результат не входят. Возникает штраф Ω(|U|) — так называемое универсальноесканирование. При больших коллекциях это означает фактический просмотр всей базы ради одного «не».
Таким образом, каждый из двух классических методов справляется со своей ограниченной ролью, но на немонотонных DAG-запросах они упираются либо во время, либо в пространство. До сих пор считалось, что это неизбежная плата за выразительность.
Алгоритм ComputePN
Амир Аавани предлагает обходной манёвр — детерминированный алгоритм ComputePN, специально заточенный под разрежённые данные. Ключевая идея в том, чтобы отделить логическое отрицание от материализации всего универсума. Вместо того чтобы строить полный список «всех документов, которых нет», ComputePN использует дуальное представление каждого узла: пара «положительное-отрицательное» хранит и то, что входит в результат, и то, что гарантированно в него не входит.
Такой подход позволяет учитывать только активные документы — те, что реально участвуют в вычислениях. Промежуточные результаты мемоизируются прямо на графе запроса, поэтому одни и те же подвыражения не пересчитываются по несколько раз. Итоговая сложность оценивается как O(|Q| · |U_active|), где U_active — множество затронутых документов, а не весь универсум.
На практике это означает, что тяжёлые случаи с отрицаниями и сходящимися ветвями перестают быть фатальными. Если реальная коллекция велика, но запрос задевает лишь небольшую её часть, ComputePN остаётся эффективным.
Что это значит для поисковых движков и ИИ
Главный вывод работы не в том, что обход инвертированного индекса принципиально невозможно ускорить. Скорее наоборот: автор показывает, как можно нативно вычислять P-полные запросы, избегая двух главных ловушек — комбинаторного разворачивания дерева и сканирования всех документов ради отрицания.
Для гибридных нейросимволических систем это важный сигнал. LLM-агенты генерируют всё более изощрённые запросы, и поисковый бэкенд должен уметь их обслуживать без катастрофической деградации. Теоретическая P-полнота остаётся предупреждением для разработчиков параллельных архитектур, но ComputePN показывает, что грамотная инженерная реализация способна обойти худшие сценарии.
Впрочем, до появления алгоритма в production-системах предстоит ещё много работы. Предложенная схема требует аккуратной работы с дуальными представлениями и мемоизацией на уровне реального поискового движка. Но то, что задача наконец получила строгую теоретическую базу, — само по себе важно: теперь разработчики хотя бы знают, с какой сложностью имеют дело и какие приёмы действительно помогают.
