倒排索引遍历的P-完全性：布尔查询DAG评估的复杂度分析

现代人工智能代理越来越多地依赖搜索基础设施来执行复杂的神经符号推理工作流。这些工作流通常会将数据编译成深度嵌套、非单调的文本字段布尔查询。

然而，针对倒排索引的标准查询评估策略在处理这类结构时面临严重的理论限制。有状态迭代器模型（一次处理一个文档）在结构上受到 NC^1 公式评估的限制，当对重新收敛的逻辑进行展开时，其查询复杂度会在最坏情况下出现 O(2^|Q|) 的指数级膨胀。

相反，递归实体化模型……