Apple établit la P-complétude des requêtes booléennes

Apple publie l’étude Le 27 août 2026, Apple Research publie un article signé Amir Aavani sur la complexité de l’évaluation des requêtes booléennes dans les index inversés. L’étude porte sur les structures utilisées par des agents d’IA pour exécuter des raisonnements neuro-symboliques via des infrastructures de recherche. Elle formalise un langage de récupération nommé L_R. Ce langage repose sur des graphes acycliques orientés, ou DAG. Les auteurs démontrent que son problème d’évaluation est P-Complète. Cette classification établit une limite théorique pour l’exécution native de logiques complexes sur un index inversé. L’article présente ensuite ComputePN pour rendre cette évaluation traitable. Lire l’étude d’Apple.

Les requêtes gagnent en profondeur Les agents d’IA compilent parfois leurs flux de raisonnement en requêtes booléennes imbriquées et non monotones sur des champs textuels. Ces requêtes peuvent contenir une logique qui converge plusieurs fois vers les mêmes sous-structures. Selon l’étude, les itérateurs Document-at-a-Time sont structurellement limités par l’évaluation de formules NC^1. Leur déroulage peut alors produire une complexité exponentielle en O(2^|Q|), où |Q| représente la taille de la requête. Les modèles Term-at-a-Time rencontrent une autre contrainte avec la négation logique. Ils peuvent nécessiter un espace Ω(|U|), correspondant à un balayage de l’univers documentaire. Cette analyse compare deux limites distinctes des stratégies courantes.

Apple formalise les limites théoriques

Le langage devient P-Complète L’article d’Amir Aavani formalise L_R avec des graphes acycliques orientés plutôt qu’avec des arbres de requêtes. Cette représentation conserve les reconvergences logiques au lieu de les dupliquer lors du calcul. Apple établit que l’évaluation de L_R est strictement P-Complète. Le résultat concerne la difficulté théorique d’exécuter nativement des requêtes booléennes complexes sur un index inversé. La démonstration situe ainsi le problème dans la classe P-Complète. Elle ne décrit pas une mesure de performance sur un jeu de données particulier. Elle définit une frontière formelle pour les méthodes de recherche qui combinent conjonction, disjonction et négation dans des structures en DAG. Voir la publication sur arXiv.

ComputePN sépare la négation Pour répondre à ces contraintes, Apple introduit ComputePN, un algorithme déterministe et sensible à la parcimonie. Sa représentation Positive-Negative découple la négation logique de la matérialisation à l’échelle de l’univers documentaire. L’algorithme exploite aussi une mémorisation native des DAG. L’étude borne alors son temps d’évaluation à O(|Q| · |U_active|). |Q| désigne la taille de la requête. |U_active| désigne l’ensemble actif de documents concernés par le calcul. Cette borne évite, selon l’article, l’expansion combinatoire des arbres et la pénalité du balayage universel. ComputePN évalue ainsi les requêtes P-Complètes directement sur l’index inversé, avec une représentation duale des résultats positifs et négatifs.

La recherche devient calcul Le résultat propose une base formelle pour le retrieval computationnel, selon la formulation de l’article. La contribution combine trois éléments précis. L_R décrit les requêtes sous forme de DAG. La preuve établit la P-Complétude de leur évaluation. ComputePN fournit ensuite une méthode bornée par |Q| et |U_active|. Cette approche vise les flux dans lesquels des agents d’IA exécutent des raisonnements complexes au moyen d’infrastructures de recherche. Le texte relie directement ces flux aux requêtes imbriquées et non monotones sur des champs textuels. La publication place donc l’index inversé au centre d’une analyse algorithmique des opérations booléennes reconvergentes et de la négation logique.