# Apple classe l’évaluation des requêtes booléennes P-complète

> Apple montre que l’évaluation de requêtes booléennes en DAG est P-Complète et présente ComputePN, borné par O(|Q| · |U_active|).

Type : Actualité IA · Catégorie : Outils · Publié le 2026-08-20 · Signal IA - Order & Chaos
Source : https://www.orderchaos.eu/signal-ia/actu/apple-etablit-la-p-completude-des-requetes-booleennes
Tags : recherche, algorithmes, index inversé, requêtes booléennes, agents ia, agents-ia, raisonnement

---

## En résumé

- Apple formalise l’évaluation des requêtes booléennes en graphes orientés acycliques.
- Les modèles existants subissent une expansion exponentielle ou un coût mémoire lié à l’univers documentaire.
- ComputePN exploite une représentation positive-négative et la mémorisation native des DAG.

**Le signal :** Apple classe l’évaluation des requêtes booléennes en DAG comme P-Complète et propose ComputePN pour limiter le temps à O(|Q| · |U_active|).

**Apple publie l’étude** Le 20 août 2026, Apple Research a publié une étude d’Amir Aavani sur la complexité du parcours dans les index inversés. Le papier examine l’évaluation de requêtes booléennes représentées par des graphes orientés acycliques, ou DAG. Il établit que le problème d’évaluation de ce langage de recherche, noté L_R, est P-Complete. Cette classification porte sur l’exécution native de logiques complexes dans un index inversé. Le sujet concerne notamment les agents IA qui utilisent des infrastructures de recherche pour exécuter des workflows de [raisonnement](/signal-ia/actu/michael-stemmle-lorchestration-redefinit-la-finance) neuro-symbolique. L’étude est disponible sur la [publication Apple](https://machinelearning.apple.com/research/the-p-completeness-of-inverted-index-traversal) et sur [arXiv](https://arxiv.org/abs/2601.18747).

**Les requêtes deviennent imbriquées** Selon Apple, ces workflows compilent souvent des requêtes booléennes profondément imbriquées et non monotones sur des champs textuels. Les stratégies classiques rencontrent alors deux limites théoriques distinctes. Le modèle Document-at-a-Time utilise des itérateurs avec état et reste structurellement borné par l’évaluation de formules NC^1. Lorsqu’une logique reconvergente est déroulée, sa complexité peut atteindre O(2^|Q|) dans le pire cas. Le modèle Term-at-a-Time suit une autre approche, fondée sur la matérialisation récursive. Pour traiter la négation logique sur l’univers documentaire, il entraîne une pénalité d’espace Ω(|U|), appelée Universal Scan. Ces limites motivent la formalisation proposée dans l’étude.

## ComputePN évite deux pénalités

**L’algorithme change la représentation** Apple présente ComputePN, un algorithme déterministe conçu pour exploiter la structure des requêtes et leur sparsité. Sa première idée consiste à découpler la négation logique de la matérialisation à l’échelle de l’univers documentaire. L’algorithme utilise pour cela une représentation duale Positive-Negative. Sa seconde idée repose sur la mémorisation native des DAG. Cette mémorisation évite de traiter plusieurs fois des sous-graphes reconvergents, selon la description du papier. ComputePN évalue ainsi des requêtes P-Complete directement sur l’index. Apple indique que cette méthode évite simultanément le goulot d’étranglement lié à l’expansion combinatoire des arbres et la pénalité du parcours universel.

**La borne dépend des actifs** La borne annoncée pour ComputePN est O(|Q| · |U_active|). Elle dépend de la taille de la requête, notée |Q|, et de l’ensemble actif de documents, noté |U_active|. Cette formulation se distingue du coût Ω(|U|) associé à la matérialisation de l’univers complet pour certaines négations. Elle se distingue aussi de l’explosion O(2^|Q|) observée lors du déroulage de logiques reconvergentes dans le modèle Document-at-a-Time. Le résultat présenté reste une propriété théorique de l’algorithme décrit par Apple. Le texte ne fournit pas, dans les éléments disponibles, de mesure expérimentale, de comparaison chiffrée avec un moteur précis ou de déploiement produit.

## Apple pose une base formelle

**La [recherche](/signal-ia/actu/bair-libere-une-promotion-ia-prete-a-conquerir) vise le retrieval** Le papier formalise un langage de recherche L_R fondé sur les DAG et en caractérise la difficulté d’évaluation. Apple présente cette formalisation comme une base pour le retrieval computationnel, c’est-à-dire l’exécution native de logiques complexes sur un index inversé. Le résultat P-Complete décrit une frontière théorique pour cette exécution. ComputePN fournit ensuite une manière déterministe d’évaluer ces requêtes avec la borne annoncée sur |Q| et |U_active|. L’étude ne transforme pas cette classification en promesse de performance générale. Elle établit plutôt un cadre, une représentation et un algorithme associés aux limites théoriques identifiées dans les modèles Document-at-a-Time et Term-at-a-Time.