La classe NP privilegia le risposte positive: se la risposta è sì, esiste una prova breve e verificabile. Ma molte domande naturali hanno la forma opposta. «Questa formula è vera per ogni assegnamento?», «Questo grafo non ha una cricca di dimensione k?», «Questo circuito si comporta correttamente su tutti gli input?». Per domande di questo tipo serve una classe speculare: coNP.
La definizione
coNP = {L : il complemento di L appartiene a NP}
In termini di certificati: un linguaggio è in coNP se le risposte negative hanno certificati brevi verificabili in tempo polinomiale. Equivalentemente, w ∈ L se e solo se per ogni stringa c di lunghezza polinomiale un certo verificatore polinomiale accetta ⟨w, c⟩.
Il confronto con NP si riassume così:
| Classe | Forma della condizione | Certificato breve per |
|---|---|---|
| NP | esiste c tale che V(w, c) | il sì |
| coNP | per ogni c vale V(w, c) | il no |
Attenzione al nome: coNP non è il complemento della classe NP, cioè non contiene «tutti i problemi che non sono in NP». Contiene i complementi dei singoli problemi di NP.
Il problema canonico: le tautologie
Una formula booleana è una tautologia se è vera per ogni assegnamento delle variabili.
TAUT = {⟨φ⟩ : φ è una tautologia}
TAUT è in coNP: se φ non è una tautologia, il certificato è un assegnamento che la rende falsa, e verificarlo è immediato. Si osservi il legame con SAT:
φ è una tautologia se e solo se ¬φ non è soddisfacibile.
Ne segue che TAUT è coNP-completo: ogni problema di coNP si riduce in tempo polinomiale a TAUT, così come ogni problema di NP si riduce a SAT. In generale, se A è NP-completo, il suo complemento è coNP-completo.
Altri esempi di problemi coNP-completi:
- insoddisfacibilità: la formula non ha alcun assegnamento che la soddisfa;
- non-hamiltonianità: il grafo non ha cicli che passino per ogni nodo una volta;
- equivalenza di circuiti: due circuiti booleani calcolano la stessa funzione su tutti gli input.
L'ultimo è un problema reale nella verifica dell'hardware: dimostrare che un circuito ottimizzato è equivalente all'originale.
NP contro coNP
Si sa che P ⊆ NP ∩ coNP, perché P è chiuso per complemento: se si risolve il sì in tempo polinomiale, si risolve anche il no. Ma non si sa se NP = coNP.
Alcuni fatti certi:
- se P = NP, allora NP = coNP, perché P = coP;
- se un problema NP-completo appartenesse a coNP, allora NP = coNP;
- quindi, se si dimostrasse NP ≠ coNP, ne seguirebbe P ≠ NP.
La congettura diffusa è NP ≠ coNP. In concreto significherebbe che non esistono certificati brevi per l'insoddisfacibilità: non c'è modo di convincere rapidamente qualcuno che una formula non ha soluzioni, almeno nel caso peggiore. Questo collega la questione alla complessità delle dimostrazioni: un sistema di prova per le tautologie in cui ogni tautologia avesse una dimostrazione di lunghezza polinomiale esiste se e solo se NP = coNP.
La zona di confine: NP ∩ coNP
I problemi in NP ∩ coNP hanno certificati brevi sia per il sì sia per il no. Per questi problemi è considerato improbabile che siano NP-completi, perché ciò implicherebbe NP = coNP.
Esempi interessanti:
- la primalità: era noto che stesse in NP ∩ coNP (un divisore certifica che un numero è composto, e i certificati di Pratt certificano che è primo) molto prima che si dimostrasse che sta in P;
- la fattorizzazione nella versione decisionale «N ha un fattore primo minore di k?»: il certificato, sia per il sì sia per il no, è la fattorizzazione completa di N, verificabile in tempo polinomiale grazie al test di primalità;
- la programmazione lineare, la cui versione decisionale ha certificati di ammissibilità e, grazie alla teoria della dualità, certificati di non ammissibilità; anche qui si è poi dimostrata l'appartenenza a P.
La storia della primalità e della programmazione lineare suggerisce che stare in NP ∩ coNP sia un buon indizio di un algoritmo efficiente ancora da trovare. Ma per la fattorizzazione nessuno lo ha trovato su computer classici.
Uno sguardo alla gerarchia polinomiale
NP corrisponde a un quantificatore esistenziale, coNP a uno universale. Si possono alternare:
- Σ₂ᵖ: esiste c₁ tale che per ogni c₂ vale V(w, c₁, c₂);
- Π₂ᵖ: per ogni c₁ esiste c₂ tale che vale V(w, c₁, c₂);
- e così via, con sempre più alternanze.
Un esempio di problema in Σ₂ᵖ: «esiste una formula con al più k simboli equivalente alla formula data?». Bisogna trovare la formula piccola (esiste) e verificare che sia equivalente su tutti gli assegnamenti (per ogni).
L'unione di tutti questi livelli si chiama gerarchia polinomiale (PH), ed è contenuta in PSPACE. Si congettura che tutti i livelli siano distinti; se due livelli consecutivi coincidessero, l'intera gerarchia collasserebbe a quel livello.
In sintesi
- coNP contiene i problemi le cui risposte negative hanno certificati brevi.
- TAUT è coNP-completo, perché φ è una tautologia se e solo se ¬φ è insoddisfacibile.
- P ⊆ NP ∩ coNP; si congettura NP ≠ coNP, che implicherebbe P ≠ NP.
- Primalità, fattorizzazione decisionale e programmazione lineare stanno in NP ∩ coNP.
- Alternando quantificatori esistenziali e universali si ottiene la gerarchia polinomiale.
