NP-completezza di SAT (Gennaio 2015)
Inviato: 28/11/2019, 14:12
Joker
Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive:
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
Credo che questa cosa la spieghi quando introduce le riduzioni, e poi la dia per scontata.
EDIT: infatti è la Proprietà 1.10.14.
Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive:
Perchè ci basta dimostrare questo?Poichè CIRCUIT SAT [math] SAT, ci basta dimostrare che CIRCUIT SAT è NP-completo,
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
Esattamente.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?
Credo che questa cosa la spieghi quando introduce le riduzioni, e poi la dia per scontata.
EDIT: infatti è la Proprietà 1.10.14.