NP-hard non è una condanna: cosa significa davvero per chi programma

Chi ha fatto un corso di algoritmi si porta dietro quasi sempre la stessa lezione: i problemi NP-hard sono, in pratica, irrisolvibili. Si dimostra che (probabilmente) non esiste un algoritmo che li risolva in tempo polinomiale su ogni input possibile, e da lì il salto mentale a "quindi lascia perdere, è una battaglia persa" è breve. È un salto sbagliato, e costa caro: capita di vedere persone abbandonare un problema di ottimizzazione reale — uno scheduling, un instradamento, una configurazione — solo perché qualcuno ha detto "è NP-hard", senza aver mai provato a scriverci sopra un algoritmo.

La dimostrazione di NP-hardness parla del caso peggiore: garantisce che esiste, da qualche parte nello spazio di tutti gli input teoricamente possibili, almeno un'istanza che farà esplodere qualunque algoritmo esatto. Non dice nulla sugli input che incontri davvero nel tuo dominio applicativo, che quasi sempre hanno una struttura molto più gentile di un input costruito apposta per far saltare un teorema.

La dependency resolution dei package manager — decidere quale combinazione di versioni di librerie installare senza conflitti — è un problema NP-hard nel caso generale. Eppure npm install, cargo o pip risolvono migliaia di grafi di dipendenze al giorno in una manciata di secondi. Il type checking di alcuni linguaggi è NP-hard nel caso generale, ma il compilatore che usi ogni giorno non si blocca mai per ore su un file normale. In entrambi i casi il caso patologico esiste sulla carta, ma quasi nessuno lo incontra mai nella pratica professionale.

Il caso più clamoroso è il SAT, il problema di soddisfacibilità booleana: l'archetipo stesso dei problemi NP-completi, quello a cui si riducono tutti gli altri. Eppure i SAT solver moderni sono così efficaci che vengono usati in produzione su scala enorme — si stima che Amazon risolva ordini di grandezza di problemi SMT (una versione ancora più complessa del SAT) al giorno per verificare configurazioni di rete e policy di sicurezza. Non per magia: per decenni di lavoro su euristiche, propagazione dei vincoli e apprendimento delle clausole in conflitto. Il progresso algoritmico, in certi ambiti, ha superato quello dell'hardware.

Prima regola: non fermarti al nome della categoria di complessità, guarda la struttura reale del tuo input. Uno scheduling con dieci task e vincoli semplici non ha nulla a che vedere, in pratica, con il caso peggiore teorico che giustifica la classificazione NP-hard — anche se formalmente appartengono alla stessa classe.

Seconda regola: hai più strumenti di quanti pensi.

// Approccio 1: euristica veloce, buona ma non ottima
function greedySchedule(tasks) {
  return tasks
    .sort((a, b) => a.deadline - b.deadline)
    .reduce(assignToFirstFreeSlot, []);
}

// Approccio 2: solver esatto su un sottoinsieme piccolo
// (es. con un SAT/SMT solver o programmazione a vincoli)
// -> pratico quando n è piccolo o la struttura è gentile

// Approccio 3: timeout + fallback
function solveWithBudget(problem, msBudget) {
  const result = exactSolver(problem, msBudget);
  return result.found ? result.solution : greedySchedule(problem.tasks);
}

Terza regola, forse la più importante: non serve la soluzione ottima in ogni caso, serve una soluzione abbastanza buona entro un tempo accettabile. Un timeout con fallback euristico è una strategia perfettamente legittima — la stessa idea di una richiesta HTTP che non torna mai: metti un limite di tempo, mostra un errore o un risultato parziale, e vai avanti. Non è una scorciatoia vergognosa, è ingegneria.