The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs

Summary

Modern artificial intelligence agents increasingly rely on search infrastructure to run complex, neuro-symbolic reasoning workflows that compile into deeply nested, non-monotonic Boolean queries. Standard inverted index evaluation methods struggle with these query structures, facing either exponential query complexity under Document-at-a-Time models or universe-scale space penalties under Term-at-a-Time models during logical negation. To address these theoretical limitations, the author formalizes a DAG-based retrieval language named L_R and proves its query evaluation problem is strictly P-Complete. The paper introduces ComputePN, a deterministic and sparsity-aware algorithm that employs a Positive-Negative dual representation alongside native DAG memoization. This mechanism bounds evaluation time to O(|Q| · |U_active|), effectively evaluating P-Complete queries natively over the index while bypassing combinatorial tree expansion and universal scan overhead.

Takeaways

1. 1

   The query evaluation problem for the DAG-based retrieval language L_R is strictly P-Complete.

2. 2

   Document-at-a-Time evaluation suffers an O(2^|Q|) exponential complexity blowup on re-convergent logic, whereas Term-at-a-Time incurs an Omega(|U|) space penalty on negation.

3. 3

   ComputePN uses a Positive-Negative dual representation and DAG memoization to bound evaluation time to O(|Q| · |U_active|), avoiding both tree-expansion bottlenecks and universal scans.