NP-completezza di SAT (Gennaio 2015)

Rispondi
Avatar utente
andrea.tosti
Messaggi: 15
Iscritto il: 02/10/2018, 9:20

Joker

Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive:
Poichè CIRCUIT SAT [math] SAT, ci basta dimostrare che CIRCUIT SAT è NP-completo,
Perchè ci basta dimostrare questo?
Io sapevo che un problema A, completo per una certa classe S, non dice nulla su un altro problema B se A [math] B. Ci dice solo che B è difficilme almeno quanto A. E' sbagliato quanto dico o c'è qualche considerazione in più da fare?

Quello che ho pensato è che visto che sappiamo che SAT appartiene a NP e che ogni problema di NP si riduce a CIRCUIT SAT, dimostrando la riduzione precedente e utilizzando la transitività delle riduzioni potrei dire che SAT è completo per NP. E' questo il ragionamento?

caos
Ciao, questa cosa funziona perchè la relazione di riduzione [math] (che abbrevierò con [math]) è transitiva, cioè se [math] se [math] e [math].
Nel nostro caso se dimostrassimo che [math] [math] e sapendo che [math] per transitività avremmo che [math] [math], ovvero [math] è [math], sapendo inoltre che [math] abbiamo anche la completezza, ovvero il teorema di Cook-Levin.

MindFlyer
Quello che ho pensato è che visto che sappiamo che SAT appartiene a NP e che ogni problema di NP si riduce a CIRCUIT SAT, dimostrando la riduzione precedente e utilizzando la transitività delle riduzioni potrei dire che SAT è completo per NP. E' questo il ragionamento?
Esattamente.
Credo che questa cosa la spieghi quando introduce le riduzioni, e poi la dia per scontata.

EDIT: infatti è la Proprietà 1.10.14.
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”