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 ,S. Fortune, "A note on sparse complete sets", SIAM Journal on Computing, volume 8, numero 3, 1979, pp. 431–433. 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.
Note
Categoria:Classi di complessità