Problema sottovincolato
Un problema sottovincolato è un problema logico con pochi vincoli tra le variabili. Nel calcolo proposizionale un problema sottovincolato è una formula in cui il rapporto tra il numero delle clausole (c) e il numero delle variabili (v) è molto basso. Ad esempio, dato uno spazio di assegnamento dei valori di verità Ω={0,1}, nella seguente formula 3-CNF il problema è composto da quattro variabili (v=4) e da quattro clausole (c=4), ognuna delle quali è una disgiunzione tra tre variabili ( letterali ). Il rapporto c/v è pari a 1.
( ¬A ∨ B ∨ C ) ∧ ( ¬B ∨ C ∨ D ) ∧ ( ¬C ∨ D ∨ A ) ∧ ( ¬D ∨ A ∨ B )
La soddisfacibilità logica (SAT) di un problema sottovincolato può essere agevolmente analizzata tramite un assegmanto casuale dei valori di verità alle variabili del problema ( es. ricerca locale proposizionale o walksat ). Nell'esempio precedente sono sufficienti pochi tentativi casuali ( random ) per giungere alla prima soluzione valida del problema e dimostrare la soddisfacibilità logica ( SAT ) della formula.
Generalmente, dato un rapporto k pari a c/v, si parla di problema sottovincolato quando il rapporto (k) tra le clausole e le variabili è uguale o inferiore a tre ( k≤3 ). Sulla base di ricerche empiriche e sperimentali, la probabilità di risolvere un problema SAT tramite l'assegnamento casuale dei valori alle variabili si riduce bruscamente quando il rapporto (k) è superiore a tre (k>3). Quando il rapporto c/v è superiore a tre la formula logica viene definita problema sovravincolato.
