riduzioni NP-completi

Question

Ho letto che "Ogni problema in NP può essere ridotto ad ogni problema NP-completo".

La mia domanda è sulla scelta della parola "ridurre". Se fossi di "ridurre" un problema polinomio in NP ad un problema esponenziale in NP, mi sento semplicemente di strano usare la parola "ridurre", perché mi sento come ho aumentato il problema, non ha ridotto. Quindi, perché usiamo la parola riduciamo?

Inoltre, il motivo per cui si scrive "riduciamo A a B" da $ A \ le_ {} p B $. Sembra all'indietro.

Answer 1

Una riduzione da A a spettacoli B che A è "no più duro" di B in un certo senso. Noi lo chiamiamo una riduzione in quanto riduce il problema di risolvere un al problema di risolvere B. Questo è un uso della parola "ridurre" che è più matematica e meno di "dimensioni"; si può pensare ad esso nel senso che abbiamo ridotto la quantità di lavoro del mondo ha a che fare, perché anche se non abbiamo risolto A o B con la riduzione che abbiamo fatto in modo che una soluzione a B verrà automaticamente anche essere una soluzione ad un.

Dove A è stato un problema che non ha avuto alcun soluzioni efficienti per, e dove abbiamo già una soluzione efficiente per B, questo risultato in una sempre più "piccolo" in un certo senso. Per esempio, diciamo che avevamo già venuta in mente una soluzione esponenziale ad A, e B è un problema NP-completo. In precedenza, il meglio che sapevo era che A era un problema di esponenziale. Dopo che qualcuno si presenta con la A - riduzione> B, ora sappiamo che è in realtà un problema NP

.

Sì, è possibile utilizzare un argomento di riduzione a dimostrare che un problema già noto-to-be-easy è "no più duro" di un problema difficile. È possibile in uso infatti una riduzione polinomiale da ANY problema in P ANY altro problema di sorta (che ha almeno un "sì" istanza e almeno un "no "esempio), perché si può 'risolvere' il problema P nella riduzione, ma semplicemente codificare la risposta come un esempio di un altro problema. Sì, questo è inutile. Ma non è "sbagliato" o incoerente.

Il problema che stai avendo è puramente nell'analogia che si sta utilizzando, e cioè che una riduzione è un "modo di fare un problema più piccolo". Questa è una metafora ragionevole per una delle solite obiettivi di prove di riduzione, che è quello di dimostrare che un problema è più "facile" di quanto precedentemente sospettato, trovando un modo per ridurlo a un altro problema già noto per essere "più facile".

Ma questo non ti aiuta con l'altro uso estremamente comune di argomenti di riduzione, che è quello di mostrare che un problema C è impossibile per risolvere, trovando una riduzione da D altro problema che è già noto per essere impossibile. Qui l'argomento riduzione non è "fare D più piccolo", è dimostrando che C è "grande".

Prova a pensare a un argomento riduzione da A -> B come un modo di mostrare che A è "no più duro" di B. Quando si pensa in quel modo, non è affatto sorprendente che spesso è possibile ridurre i problemi facili per quelli duri; sapevamo già che erano più facili! Questo account anche spiega facilmente le prove incomputabilità di riduzione; se l'arresto problema non è più difficile di quanto X, allora X non può essere risolvibile.

Answer 2

Per lo più dal commento di Vor:

$ A \ le_pB $ possono essere adottate per significare che il problema $ A $ è almeno altrettanto facile da $ B $ (o meno difficile). Il $ _p $ pedice sta per polinomiale e indica che "facile" è relativo termine qui, e la difficoltà dei problemi reali deve considerare il polinomiale Riduzione come irrilevanti (come quando risolvere i $ B $ richiede tempo super-polinomiale).