Researchers prove Boolean query evaluation over search indices is computationally hard—and offer a fix

AI systems increasingly rely on search engines to ground neuro-symbolic reasoning, but they often generate deeply nested Boolean queries with negation and re-convergent logic. These queries can overwhelm standard search evaluation strategies, creating a mismatch between what modern retrieval systems need to support and what existing algorithms can efficiently deliver.

The challenge with complex queries#

Current approaches to evaluating Boolean queries over inverted indices face fundamental computational limits. Stateful document-at-a-time iterators can structurally expand exponentially—suffering worst-case blowup of $O(2^{|Q|})$ when unrolling re-entrant logic in nested queries. Recursive term-at-a-time materialization, meanwhile, requires scanning the entire document universe when handling negation, incurring an $\Omega(|U|)$ space penalty that becomes prohibitive at scale.

A new theoretical framework#

Researchers from arXiv have now formalized these limits. They define a retrieval language based on Directed Acyclic Graphs (DAGs) and prove that the problem of evaluating such queries is P-Complete—meaning it lies at the hardest tier of deterministic polynomial-time solvable problems. This theoretical result clarifies why no simple algorithm can dodge the underlying difficulty.

A practical solution: ComputePN#

To make complex query evaluation tractable in real systems, the authors introduce ComputePN, a deterministic algorithm that decouples negation from universe-scale materialization. The key innovation is a Positive-Negative dual representation that avoids explicit scanning of the full document space, combined with native DAG memoization. The result is an evaluation time bounded by $O(|Q| \cdot |U_{\mathit{active}}|)$—linear in both query size and only the subset of documents relevant to the computation.

Why it matters#

This work bridges theory and practice: it establishes fundamental hardness boundaries for retrieval over indices, while simultaneously showing that P-Complete queries can be evaluated natively without either combinatorial tree expansion or universal scans. The framework provides a formal foundation for next-generation retrieval systems that can handle the kinds of complex, non-monotonic logical queries that modern AI applications require.