Co-NP-completo

Nella teoria della complessità computazionale, i problemi computazionali che sono co-NP-completi sono i problemi più difficili in co-NP, nel senso che sono quelli che hanno le maggiori probabilità di non essere nella classe P. Se esiste un modo di risolvere rapidamente un problema co-NP-completo, allora quell'algoritmo può essere usato per risolvere rapidamente tutti i problemi co-NP.

Ciascun problema co-NP-completo è il complemento di un problema NP-completo. Ci sono problemi sia in NP sia in co-NP, ad esempio tutti i problemi in P o di fattorizzazione degli interi, tuttavia non si sa se gli insiemi sono uguali, sebbene la disuguaglianza sia ritenuta più probabile. Vedi co-NP e NP-completo per maggiori dettagli.

Fortune mostrò nel 1979 che se un qualsiasi linguaggio sparso è co-NP-completo (o anche solo co-NP-difficile), allora P = NP, un fondamento critico per il teorema di Mahaney.

Definizione formale

Un problema decisionale C è co-NP-completo se è in co-NP e se ogni problema in co-NP è riducibile ad esso molti a uno in tempo polinomiale. Questo significa che per ogni problema co-NP L, esiste un algoritmo in tempo polinomiale che può trasformare qualsiasi istanza di L in un'istanza di C con lo stesso valore di verità. Come conseguenza, se avessimo un algoritmo in tempo polinomiale per C, potremmo risolvere tutti i problemi co-NP nel tempo polinomiale.

Esempio

Un esempio semplice di problema co-NP-completo è la tautologia, il problema di determinare se una data formula booleana è una tautologia; cioè, se ogni possibile assegnazione di valori veri/falsi a variabili produce un'affermazione vera. Questo è strettamente legato al problema di soddisfacibilità booleana, che chiede se esista "almeno una" assegnazione siffatta. Si noti che il problema della tautologia per le formule booleane positive rimane co-NP completo, anche se il problema della soddisfacibilità è banale, in quanto ogni formula booleana positiva è soddisfacibile.