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,[1] 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
- ^ S. Fortune, "A note on sparse complete sets", SIAM Journal on Computing, volume 8, numero 3, 1979, pp. 431–433.
V · D · M | |
---|---|
P · NP · co-NP · NP-C · co-NP-C · NP-hard · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · Co-RE · RE-C · Co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH |