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

Introduces ComputePN, a deterministic, sparsity-aware evaluation algorithm for Boolean query DAGs over inverted indices. This algorithm decouples logical negation from universe-scale materialization using a novel Positive-Negative dual representation and native DAG memoization, bounding evaluation time to O(|Q| · |U_active|). This enables the evaluation of P-Complete queries natively over the index, addressing limitations of stateful iterator and recursive materialization models.