NP-completezza di SAT

Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive:
Poichè CIRCUIT SAT [tex]\leqslant[/tex] 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 [tex]\leqslant[/tex] 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?

Comments

  • caoscaos Posts: 9
    edited March 27
    Ciao, questa cosa funziona perchè la relazione di riduzione [tex]\leq_{LOGSPACE}[/tex] (che abbrevierò con [tex]\leq[/tex]) è transitiva, cioè se [tex]\forall A,B,C[/tex] se [tex]A \leq B[/tex] e [tex]B \leq C \Rightarrow A \leq C[/tex].
    Nel nostro caso se dimostrassimo che [tex]\forall I \in NP[/tex] [tex] I \leq CIRCUIT SAT[/tex] e sapendo che [tex]CIRCUIT SAT \leq SAT[/tex] per transitività avremmo che [tex] \forall I \in NP[/tex] [tex]I \leq SAT [/tex], ovvero [tex]SAT[/tex] è [tex]NP-arduo[/tex], sapendo inoltre che [tex]SAT \in NP[/tex] abbiamo anche la completezza, ovvero il teorema di Cook-Levin.
    Source
  • MindFlyerMindFlyer Posts: 436
    edited January 2015
    Joker wrote: »
    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.
Sign In or Register to comment.