La congettura

Sulla base del testo di Garey e Johnson (1979), presento ora la congettura dell’in- trattabilit`a della logica proposizionale classica per poterne sottolineare l’opposi- zione al presunto carattere tautologico delle inferenze proposizionali classiche.

In generale, un problema di decisione `e una domanda che ammette una risposta positiva o negativa ed `e rappresentato da una classe di stringhe di simboli, dove ciascuna stringa identifica una istanza particolare del problema. Ad esempio, il problema della tautologia (Taut) `e rappresentato dall’insieme di formule ben formate di un linguaggio logico standard, ogni enunciato `e un’istanza del problema la cui soluzione `e positiva (indicata da 1) se la stringa in questione `e una tautologia oppure una risposta negativa (0) se non lo `e.

Un algoritmo `e una procedura meccanica che risolve un problema di decisione se fornisce una soluzione per ogni istanza del problema. Il fattore principale per determinare l’efficienza di un algoritmo `e il tempo necessario per eseguirlo. La funzione di complessit`a temporale di un algoritmo misura il numero massimo di passi che l’algoritmo deve eseguire per ogni possibile lunghezza dell’input. La lunghezza dell’input di un’istanza di un problema `e definita dal numero di simboli che codificano l’istanza in questione.

Una funzione f (n) `e O(g(n)) ogni volta che esiste una costante c tale che |f (n)| ≤ c|g(n)| per ogni n ≥ 0. Un algoritmo `e detto di tempo polinomiale se la sua funzione di complessit`a temporale `e O(p(n)) per qualche funzione polinomiale p, dove n rappresenta la lunghezza dell’input. Qualunque algoritmo la cui funzione

di complessit`a temporale non pu`o essere rappresentata in questo modo `e detto di tempo esponenziale.

Un problema di decisione `e detto trattabile, e cio`e risolvibile in pratica, se pu`o essere risolto da un algoritmo di tempo polinomiale; altrimenti `e detto intrattabile. P `e la classe di tutti i problemi di decisione che possono essere risolti in tempo polinomiale da algoritmi deterministici, e cio`e da algoritmi che definiscono, ad ogni passo dell’esecuzione, una e una sola operazione da svolgere al passo successivo.

Complementare al problema della tautologia `e il problema della soddisfacibi- lit`_{a (Sat): data una formula booleana che esprime un enunciato B, Sat consiste} nel determinare se esiste una valutazione delle proposizioni atomiche che occor- rono in B tale che B sia vero. Dato che una formula `e vera se e solo se la sua negazione `e falsa, una formula `e soddisfacibile se e solo se la sua negazione non `e una tautologia.

Per risolvere un’istanza del problema Sat, `e necessario impiegare un algoritmo non deterministico, e cio`e un algoritmo costituito da due fasi separate: la prima, detta fase di supposizione, assegna una valutazione casuale alle proposizioni ato- miche dell’enunciato in questione; la seconda, detta fase di controllo, verifica se tale valutazione rende vero l’enunciato. La funzione di complessit`a temporale di un algoritmo non deterministico misura il numero massimo di passi che l’algoritmo deve eseguire per ogni possibile lunghezza dell’input, nel caso in cui le supposi- zioni conducono a fornire una risposta positiva al problema. NP `e la classe dei problemi di decisione che possono essere risolti in tempo polinomiale da un al- goritmo non deterministico: intuitivamente, NP include tutti i problemi per cui `

e possibile verificare in tempo polinomiale la correttezza di una presunta prova che la soluzione sia positiva. Il problema della soddisfacibilit`a appartiene a NP: una valutazione che rende vero un enunciato `e interpretata come una prova della soddisfacibilit`a dell’enunciato in questione, la cui correttezza pu`o essere verificata in tempo polinomiale.

La relazione che sussiste tra le classi P e NP `e la pi`u grande delle questioni irrisolte nella teoria della complessit`a computazionale. Da un lato, `e chiaro che tutti i problemi di decisione appartenenti alla classe P sono inclusi in NP, perch´e qualunque algoritmo deterministico pu`o essere impiegato come fase di controllo di un algoritmo non deterministico. Dall’altro lato per`o non `e stato ancora dimo- strato n´e che P = NP, n´e che P 6= NP. Tuttavia, la maggior parte dei ricercatori assume che P 6= NP e impiega questa congettura come se fosse stata dimostra-

ta: ci`o significa che comunemente si assume che non sia possibile trovare, per ogni problema in NP, un algoritmo deterministico in grado di risolverlo in tempo polinomiale.

Ci`o vale in particolare per i problemi NP- completi, ossia i problemi pi`u difficili della classe NP. Un problema di decisione Π `e detto NP-completo se e solo se Π appartiene a NP e ogni problema di decisione Π0 ∈ NP pu`o essere trasformato in tempo polinomiale in Π, vale a dire esiste un algoritmo di tempo polinomiale per tradurre ogni istanza I0 di Π0 in un’istanza I di Π in modo tale che I0 `e un’istanza positiva di Π0 se e solo se I `e un’istanza positiva di Π. I problemi NP-completi sono equivalenti nel senso che possono essere mutualmente trasformati in tempo polinomiale.

Di conseguenza, se si riuscisse a trovare un algoritmo deterministico di tempo polinomiale in grado di risolvere un problema NP-completo, e cio`e se un proble- ma NP-completo appartenesse a P e fosse quindi trattabile, allora si potrebbe concludere l’appartenenza di tutti i problemi di NP in P, vale a dire si potrebbe dedurre la trattabilit`a di tutti i problemi di NP. Tuttavia, la congettura P 6= NP porta ad assumere che tutti i problemi NP-completi siano intrattabili.

Cook (1971) fonda la teoria della completezza NP dimostrando che in un lin- guaggio booleano standard il problema della soddisfacibilit`a `e NP-completo. `E quindi altamente probabile che Sat sia un problema intrattabile. Inoltre, dato che un enunciato `e una tautologia se e solo se la sua negazione non `e soddisfacibile, an- che il problema della tautologia `e verosimilmente intrattabile, cio`e non risolvibile nella pratica, dal momento che appartiene alla classe di problemi co-NP-completi.