La valutazione su indici invertiti è P-completa, ma i DAG la rendono gestibile.
Ci sono assunzioni silenziose che reggono il web. Una di queste è che rispondere a una query — trovare i documenti giusti dentro un archivio — sia un problema per cui la tecnologia ha già trovato una risposta efficiente. Lo scorso 26 gennaio, però, un preprint ha smontato questa convinzione. Il paper di Amir Aavani, sottomesso su arXiv, formalizza un linguaggio di retrieval basato su Directed Acyclic Graphs — i DAG, grafi aciclici orientati — e dimostra che il suo problema di valutazione è P-completo. Ad agosto lo stesso risultato è stato pubblicato anche sul sito ufficiale di machine learning research di Apple. Non è un dettaglio: significa che una delle aziende più interessate a capire quanto costa cercare ha deciso di mettere il teorema in vetrina.
La query impossibile: il lato oscuro dell’indice invertito
La cosa sorprendente del risultato è che riguarda uno strumento che sembra banale. Un indice invertito è il meccanismo che consente a un motore di ricerca di passare da una parola alla lista dei documenti che la contengono. Funziona da decenni, è alla base di quasi tutto ciò che chiamiamo “cercare”. Eppure, quando lo si osserva attraverso un linguaggio di retrieval formale basato su DAG, la valutazione delle query diventa un problema P-completo.
Che cosa significa, in pratica? La classe P raccoglie i problemi risolvibili in tempo polinomiale, cioè in un numero di passi che cresce come una potenza della dimensione dell’input. I problemi P-completi sono i più difficili entro questa classe: non è scontato che aggiungere processori serva a velocizzarli, perché non si lasciano facilmente spezzare in parti indipendenti. Se la valutazione può esplodere, ogni query ha un costo che qualcuno deve pagare.
Qui entra ComputePN, l’algoritmo proposto da Aavani. L’algoritmo fissa un tetto al tempo di valutazione: O(|Q| * |U_active|), dove |Q| è la dimensione della query e |U_active| è l’insieme dei documenti attivamente coinvolti. In altri termini, il costo cresce con la ricchezza della domanda e con la porzione di archivio che tocca, non con l’intero universo indicizzato. Ci riesce separando la negazione logica dalla materializzazione su scala universale, attraverso una rappresentazione duale positiva-negativa, e sfruttando la memoizzazione nativa del DAG. Resta una domanda aperta: perché un problema P-completo non è una condanna definitiva per la ricerca reale?
Perché “P-completo” non vuol dire “lento per sempre”
La storia della teoria della complessità aiuta a ridimensionare il panico. Nel 1975 Richard Ladner aveva dimostrato che il Circuit Value Problem — valutare un circuito booleano aciclico — è P-completo rispetto alle riduzioni log-spazio, come spiega un handout della Cornell University. Ma nel 1987 Sam Buss ha mostrato, come riportato nella versione aggiornata del paper, che il Boolean Formula Value Problem — la stessa valutazione, ristretta alle formule booleane anziché ai circuiti generali — sta in ALOGTIME/NC^1, una classe molto più trattabile e parallelizzabile.
Il punto è questo: la complessità non è una proprietà fissa del problema, dipende dalla struttura. Un DAG è una struttura rigida, in cui i nodi sono connessi in una direzione sola e non ci sono cicli. Ed è proprio quella rigidità, sfruttata dalla memoizzazione nativa di ComputePN, a rendere governabile ciò che in astratto sembra esplodere. Il risultato di Aavani non dice che la ricerca è condannata. Dice che il modo in cui si struttura la query e l’indice determina quanto il problema sia gestibile. E questa è una notizia per chi progetta motori di ricerca, ma anche per chi ci vive sopra.
Apple, Vespa e la guerra silenziosa per il costo della ricerca
E qui si gioca la partita industriale. Ad agosto 2026, Apple ha pubblicato il risultato teorico sulla complessità dell’attraversamento degli indici invertiti sul suo sito ufficiale di Machine Learning Research. Non è un annuncio di prodotto: è un segnale di direzione. Un’azienda di quel peso non mette in vetrina un teorema sulla complessità per caso.
Dall’altro lato c’è Vespa, il motore di ricerca open source nato in Yahoo. Nei giorni scorsi il blog di Vespa ha descritto un metodo ibrido su scala miliardaria che combina la ricerca approssimata dei vicini più prossimi basata su grafi HNSW — una struttura che organizza i vettori in strati per trovare rapidamente quelli simili — con un file invertito su disco. Va preso per quello che è: il racconto di un’azienda che descrive la propria soluzione, non una verifica indipendente. Ma il movimento racconta qualcosa.
Da una parte la teoria fissa i limiti: cosa si può valutare, a quale costo. Dall’altra l’ingegneria cerca di conviverci: Vespa combina ciò che sta in memoria con ciò che resta su disco, perché non tutto può essere indicizzato allo stesso prezzo. Il controllo della complessità determina chi può indicizzare e scalare. Per chi pubblica contenuti e vive di visibilità nei motori di ricerca, la domanda cambia: se il costo non sta più solo nel crawling — nello scandagliare il web per raccogliere le pagine — ma anche nella valutazione delle query, allora l’indicizzazione diventa innanzitutto una questione di economia computazionale. La ricchezza del linguaggio di retrieval con cui un motore interroga il proprio indice non è gratuita: ogni operatore logico, ogni negazione, ogni composizione ha un prezzo.
Il costo computazionale della ricerca non è più confinato ai data center. Definisce cosa è indicizzabile, quanto può essere ricco un linguaggio di retrieval e, in ultima analisi, chi resta visibile. Chi pubblica online dovrebbe leggere questi segnali come un cambio di regole, non come una curiosità accademica. La prossima volta che qualcuno parla di ottimizzazione per i motori di ricerca, vale la pena ricordare che il motore, prima di classificare, deve poter calcolare. E calcolare — ora c’è una dimostrazione formale — non è banale.
