📖 AI 总结

本文探讨了现代AI代理在神经符号推理工作流中，于倒排索引上执行复杂布尔查询所面临的理论计算极限。研究发现，传统的文档级迭代模型受限于NC¹公式求值，在最坏情况下会遭遇O(2^|Q|)的指数级查询复杂度爆炸；而词项级递归物化模型在逻辑否定求值时，则需承担Ω(|U|)的全集扫描空间开销。为突破上述瓶颈，作者形式化定义了基于有向无环图的检索语言L_R，并证明其求值问题严格属于P完全类。在此基础上，论文提出ComputePN算法，通过正负对偶表示将逻辑否定与全集物化解耦，并借助原生DAG记忆化，将求值时间严格限制在O(|Q|·|U_active|)。该算法能在索引上原生执行P完全查询，同时规避组合树展开与全集扫描两大缺陷，为计算检索奠定了形式化基础。