P-Completeness of Inverted Index Traversal: On the Complexity of Boolean Query DAG Evaluation

Modern AI agents rely heavily on search infrastructure to execute complex neuro-symbolic reasoning workflows. These workflows compile into deeply nested, non-monotonic Boolean queries over text fields, but existing inverted index evaluation strategies face theoretical limits.

The existing Document-At-A-Time (DAT) model is structurally limited by NC^1 formula evaluation, suffering from worst-case O(2^|Q|) exponential blowup when unfolding re-convergence logic. In contrast, the Term-At-A-Time (TAT) model incurs an Ω(|U|) space complexity penalty (universal scan) when evaluating logical negation over the document universe.

This study establishes the theoretical boundaries for natively executing complex logic on inverted indexes. It formalizes a DAG-based search language (L_R) and proves that its evaluation problem is strictly P-Complete. To address this, it introduces a deterministic, sparsity-aware evaluation algorithm called ComputePN.

ComputePN decouples logical negation from universe-scale materialization through a Positive-Negative (P-N) dual representation and leverages native DAG memoization. This strictly bounds evaluation time to O(|Q| · |U_active|), avoiding both combinatorial tree expansion bottlenecks and universal scan penalties. This lays the formal foundation for computational retrieval.