Se un problema X (problema decisionale) è noto per essere NP-Completo, e dimostrato di essere ridotto al problema Y, puoi quindi dire che il problema Y è NP-Completo?

Question

Se un problema X (problema di decisione) è noto per essere NP-Completo e si è dimostrato ridotto al problema Y in tempo polinomiale, puoi dire che il problema Y è NP-Completo?

Il mio primo pensiero è stato, no, il problema Y deve essere dimostrato che è in NP. Ma dopo un'ulteriore riflessione, se X è ridotto a Y, Y è già considerato come NP-Completo. Ora sono solo confuso ... ogni aiuto sarebbe apprezzato.

Answer 1

Argumentum per contrarium:

Se X ∈ NP e X ⇔ Y e Y ∉ NP allora X ∉ NP.

Answer 2

Problema X - Incerto
Problema Y - In NP

Per dimostrare X è in NP, è dimostrare che è possibile seguire provvedimenti per ridurre ogni problema in X ad un problema in Y. Poi si sa che il Il problema con X è almeno tanto difficile quanto il problema Y equivalente.

Quindi no, è necessario iniziare con Y e quindi ridurre a X.

Answer 3

SAT può essere risolto in una singola chiamata a tutti, ma questo non significa che tutto è in NP.

Answer 4

Sì, è corretto. È possibile ridurre il problema in tempo polinomiale a qualsiasi problema NP completo già noto, ma questo è considerato un compito molto difficile. Quindi, invece, scegli un problema già NP completo e lo riduci al tuo problema e mostra anche che è in NP, quindi il tuo problema sarà NP completo.

Answer 5

Non ancora, avrete bisogno di un paio di passi

Al fine di dimostrare che un problema L è NP-completo, abbiamo bisogno di fare le seguenti operazioni:

1. dimostrare il vostro problema L appartiene a NP (che è che, data una soluzione è possibile verificare in tempo polinomiale)
2. Selezionare un noto problema NP-completo L '
3. Descrivete un algoritmo che trasforma f L' in L
4. Pro ve che il vostro algoritmo è corretto (formalmente: x ∈ L' se e solo se f (x) ∈ L)
5. Dimostrare che algo f viene eseguito in tempo polinomiale

Finora avete passo 2,3, 4
È ancora necessario mostrare che la riduzione è polinomiale (passaggio 5)
E che il problema appartiene a NP (passaggio 1), ovvero una soluzione può essere verificata in tempo polinomiale.