复杂布尔查询的理论边界与新算法

现代AI智能体在执行推理任务时，越来越多地依赖搜索系统作为底层基础设施。这些推理工作流通常会被编译为针对文本字段的深度嵌套布尔查询，其中包含复杂的非单调逻辑结构。然而，传统倒排索引在面对此类查询时，无论采用哪种主流评估策略，都会遭遇严重的理论性能瓶颈，制约了AI智能体在实际检索场景中的推理能力。

论文首先剖析了两类主流评估模型的固有局限。基于状态迭代器的逐文档模型（Document-at-a-Time）在结构上受限于NC^1公式评估，当展开重收敛逻辑时，查询复杂度最坏情况下会出现O(2^|Q|)的指数级膨胀。而基于递归物化的逐词项模型（Term-at-a-Time）在对文档全集执行逻辑否定时，则会引入Ω(|U|)的空间复杂度代价，即所谓的「全量扫描」问题。两种模型各有其无法回避的理论上限。

为从根本上厘清问题边界，研究团队基于有向无环图（DAG）形式化定义了检索语言L_R，并通过严格的理论证明确认其评估问题属于P完全问题。这一结论意味着，在标准并行计算模型下，该类查询的评估不存在高效并行化的通用解法，从而为后续算法设计提供了明确的理论约束框架，也为计算检索领域奠定了形式化基础。

针对上述理论瓶颈，论文提出了确定性稀疏感知评估算法ComputePN。该算法的核心创新在于引入正负双重表示机制，将逻辑否定操作与全量文档集物化彻底解耦，使得否定运算无需遍历整个文档宇宙即可完成。与此同时，算法利用DAG原生的记忆化特性，避免了重复子查询的冗余计算，将整体评估时间严格控制在O(|Q|·|U_active|)，其中|U_active|仅指实际参与计算的活跃文档集合规模。

ComputePN算法的提出，使得P完全查询得以在倒排索引上原生执行，同时绕开了组合树展开导致的指数级复杂度爆炸和全量扫描带来的空间代价。这不仅在理论层面填补了复杂检索语言形式化分析的空白，也为构建能够支持深度神经符号推理的下一代搜索基础设施提供了可落地的算法路径，对AI智能体在信息检索场景中的实际部署具有重要的工程参考价值。

要点

• 基于DAG的检索语言L_R的评估问题被严格证明为P完全问题，从理论上界定了倒排索引原生执行复杂布尔查询的计算边界。
• 逐文档模型存在指数级查询复杂度膨胀风险，逐词项模型存在全量文档扫描的空间代价，两类主流策略均有无法回避的理论瓶颈。
• 新算法ComputePN通过正负双重表示与DAG记忆化机制，将评估时间限定为O(|Q|·|U_active|)，有效规避了两类传统模型的性能缺陷。
• 该研究为支持AI智能体复杂神经符号推理工作流的搜索基础设施建设提供了形式化理论基础和可行算法方案。