The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs
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