Problema sovravincolato
Un problema sovravincolato è un problema logico con molti vincoli tra le variabili. Nel calcolo proposizionale un problema logico sovravincolato è una formula logica in cui il rapporto tra il numero di clausole e il numero delle variabili è molto alto. Sulla base dei risultati sperimentali una formula logica è detta sovravincolata quando il rapporto tra il numero delle clausole (c) e il numero delle variabili (v) è maggiore di tre (c/v>3). Il rapporto c/v è molto alto e, pertanto, il problema è sovravincolato e complesso. Ad esempio, data una formula logica composta da 20 clausole (c=20) e da 4 variabili (v=4), il rapporto c/v è pari a 4 e il problema è sovravincolato. Il rapporto c/v è generalmente indicato con la variabile k. Nel caso dei problemi sovravincolati non è facile individuare la soddisfacibilità logica del problema mediante un'esplorazione casuale dell'assegnazione dei valori alle variabili ( es. random k-sat, ricerca locale proposizionale o walksat ). È molto elevata la probabilità di incappare in un fallimento. Empiricamente la probabilità si riduce rapidamente quando il rapporto c/v è pari a 4,3.
Nella teoria della complessità un problema k-Sat, un valore k superiore a tre (k>3) è considerato un problema NP-completo. Per verificare la soddisfacibilità di un problema k-Sat con k>3 tramite un algoritmo DPLL sarebbe necessario un tempo esponenziale. È invece più facile risolvere i problemi k-Sat aventi il valore k uguale o inferiore a tre (k<3) detti problemi sottovincolati. Per questa ragione la soglia di caduta della probabilità Sat è spesso utilizzata nelle teorie computazionali per distinguere i problemi facili (k<3), detti problemi sottovincolati, dai problemi complessi (k>3), detti problemi sovravincolati. In conclusione, il rapporto tra le clausole (vincoli) e le variabili di una formula logica proposizionale CNF consentono di misurare la complessità computazionale del problema.
Transizione di fase. È importante notare che i risultati empirici evidenziano un picco massimo di complessità intorno al rapporto 4,3. Ciò equivale a dire che nel punto di soglia la complessità del problema raggiunge il suo massimo. Per valori c/v superiori alla soglia, la complessità tende a scendere, pur restando comunque elevata. I casi più difficili da risolvere, quelli che impiegano un maggiore tempo di esecuzione dell'algoritmo, non sono i problemi sovravincolati bensì le situazioni intermedie, quelle con un rapporto c/v intorno alla soglia di transizione di fase (4,3). Nei problemi sottovincolati l'algoritmo può trovare rapidamente una soluzione ( soddisfacibilità logica ). Nei problemi sovravincolati può giungere rapidamente alla conclusione che il problema non ha soluzioni. Nei casi intermedi, invece, si verifica la maggiore incertezza sull'esistenza o meno delle soluzioni, poiché le rispettive probabilità tendono a eguagliarsi. La curva della complessità computazionale ( curva rossa ) è generalmente misurata in termini di tempo di esecuzione dell'algoritmo.
