证明复杂布尔查询在倒排索引上是P完全问题，提出高效求解算法。
The $\mathbf{P}$-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
- 用有向无环图建模复杂布尔查询，形式化检索语言
- 证明查询求解为P完全问题，存在指数级计算瓶颈
- 提出ComputePN算法，避免全量扫描和组合爆炸
现代AI代理依赖搜索基础设施执行复杂的神经符号推理流程。这些流程常被编译为深度嵌套、非单调的文本字段布尔查询。然而，标准倒排索引查询评估策略在处理此类结构时面临严重理论限制：基于状态的迭代器模型（文档逐个处理）受NC¹公式求值结构约束，展开重汇聚逻辑时最坏情况下的查询复杂度呈2^{|Q|}指数增长；而递归物化模型（词项逐个处理）在评估逻辑否定时需承受Ω(|U|)的空间开销（即全集扫描）。本文正式定义基于有向无环图（DAG）的检索语言（ℒ_R），并证明其求解问题是严格意义上的P完全问题。为使求解可操作，提出 exttt{ComputePN}算法——一种确定性、稀疏感知的评估方法。通过创新性的正负双表示解耦逻辑否定与全集物化，并结合原生DAG记忆化技术， exttt{ComputePN}将求解时间严格控制在O(|Q| · |U_{active}|)内。该方法成功实现对P完全查询的原生索引求解，规避了组合树膨胀瓶颈与全集扫描代价，奠定了计算检索的理论基础。
原文摘要 · Abstract (English)
Modern AI agents increasingly rely on search infrastructure to execute complex, neuro-symbolic reasoning workflows. These workflows often compile into deeply nested, non-monotonic Boolean queries over text fields. However, standard query evaluation strategies over inverted indices face severe theoretical limits when handling these structures. Stateful iterator models (Document-at-a-Time) are structurally bounded by $\text{NC}^1$ formula evaluation, suffering a worst-case $O(2^{|Q|})$ exponential blowup in query complexity when unrolling re-convergent logic. Conversely, recursive materialization models (Term-at-a-Time) incur an $Ω(|U|)$ space complexity penalty (the Universal Scan) when evaluating logical negation over the document universe. In this paper, we establish the theoretical boundaries of executing complex logic natively over an inverted index. We formalize a retrieval language ($\mathcal{L}_R$) based on Directed Acyclic Graphs (DAGs) and prove that its evaluation problem is strictly \textbf{$\mathbf{P}$-Complete}. To make evaluation tractable, we introduce \texttt{ComputePN}, a deterministic, sparsity-aware evaluation algorithm. By decoupling logical negation from universe-scale materialization via a novel Positive-Negative dual representation, and utilizing native DAG memoization, \texttt{ComputePN} strictly bounds evaluation time to $O(|Q| \cdot |U_{\mathit{active}}|)$. This approach successfully evaluates $\mathbf{P}$-Complete queries natively over the index, avoiding both the combinatorial tree-expansion bottleneck and the universal scan penalty, laying the formal foundation for computational retrieval.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。