I problemi NP-hard che non sono NP-completi sono più difficili?

Question

Dalla mia comprensione, tutti i problemi NP-completi sono NP-hard ma alcuni problemi NP-hard sono noti per non essere NP-complete, e i problemi NP-hard sono almeno altrettanto difficili dei problemi NP-complete.

I problemi NP di livello medio che non sono NP-completi sono più difficili? E com'è più difficile?

Answer 1

Da http://en.wikipedia.org/wiki/NP-hard#Examples

Ci sono anche problemi di decisione che sono NP-hard ma non NP-completo, ad esempio, il problema della terminazione. Questo è il problema che richiede "dato un programma e il suo input, funzionerà per sempre?" Questa è una domanda si/no, quindi questo è un problema decisionale. È facile dimostrare che il problema dell'arresto è NP-hard ma non NP-complete.

Answer 2

Il set di problemi NP-hard è un superset del set di problemi NP-complete. Esistono classi di complessità più "difficili" di NP, ad esempio PSPACE, EXPTIME o EXPSPACE e tutte queste contengono problemi NP-hard ma non NP-complete.

Answer 3

Per rispondere a questa domanda, è necessario prima capire quali problemi di NP-hard sono anche NP-completi. Se un problema NP-hard appartiene a set NP, allora è NP-completo. Appartenere a impostare NP, un problema deve essere

(i) un problema decisionale,
(ii) il numero di soluzioni al problema dovrebbe essere finito e ogni soluzione deve essere di lunghezza polinomiale, e
(iii) data una soluzione di lunghezza polinomiale, dovremmo essere in grado di dire se la risposta al problema è sì/no

Ora, è facile vedere che potrebbero esserci molti problemi NP-hard che non appartengono al set NP e sono più difficili da risolvere. Come esempio intuitivo, la versione di ottimizzazione del venditore ambulante in cui è necessario trovare un programma effettivo è più difficile della versione a decisione del commesso viaggiatore in cui abbiamo solo bisogno di determinare se esiste un programma con lunghezza < = k oppure no.

Answer 4

Il problema di arresto della macchina di dissaldamento è indecidibile su macchine di Turing e NP-hard, ma non NPC. Apparentemente è più difficile;)

Answer 5

Il problema di interruzione di Turing è indecidibile e appartiene al set NP-Hard. Per risolvere il problema di turing non abbiamo alcun decisore in quanto è un linguaggio RE. Quindi non abbiamo alcun algoritmo per risolverlo. Quindi è chiaro che i problemi irrisolvibili sono anche in NP-Hard set. Quindi il set NP-Hard contiene anche le lingue oi problemi per i quali non abbiamo alcun algoritmo da risolvere.

Answer 6

1. NP-completo deve essere NP e NP-rigido.
2. e NP-hard che non sono NP-completi non sono NP.
3. Ora per definizione di NP c'è qualcuno che fornisce l'istanza di risposta per il problema. e c'è un verificatore da verificare.
4. significa che NP-Hard non ha nessuno dei due. Quindi sono difficili da risolvere è vero.