Come posso verificare una soluzione al problema del commesso viaggiatore in tempo polinomiale?

Question

Quindi, TSP (problema del commesso viaggiatore) problema di decisione è NP completa .

Ma io non capisco come posso verificare che un dato soluzione a TSP è infatti ottimale in tempo polinomiale, visto che non c'è modo di trovare la soluzione ottimale in tempo polinomiale (che è perché il problema non è in P )?

tutto ciò che potrebbe aiutarmi a vedere che la lattina di verifica, infatti, essere fatto in tempo polinomiale?

Answer 1

Per essere più precisi, noi non sappiamo se TSP è nella $ \ mathsf {P} $. E 'possibile che si può essere risolto in tempo polinomiale, anche se forse la convinzione comune è che $ \ mathsf {P} \ neq \ mathsf {NP} $. Ora, ricordare che cosa significa per un problema da $ \ {mathsf NP} $ - duro e $ \ {mathsf NP} $ - completo, vedi ad esempio il mio risposta qui . Credo che la vostra fonte di confusione deriva dalle definizioni:. Un $ \ {mathsf NP} $ - problema difficile non è necessariamente in $ \ {mathsf NP} $

Come si e la pagina di Wikipedia si collega Stati, il problema di decisione è $ \ mathsf {NP} $ - completo: visti i costi e un intero $ x $, decidere se ci è un tour più conveniente che $ x $ . Un modo di vedere il problema è nella $ \ {mathsf NP} $ è vedere che data una soluzione, è facile verificare in tempo polinomiale se la soluzione è più conveniente di $ x $. Come si può fare questo? Basta seguire il tour dato, registrare il suo costo totale e, infine, confrontare il costo totale a $ x $.

Answer 2

Il punto cruciale è che si deve prendere in considerazione il decisione problema:

commesso viaggiatore Problema (decisione Version). Dato un grafo pesato G e un costo di destinazione C , c'è un ciclo hamiltoniano in < em> G il cui peso è al massimo C

Per un 'sì' esempio, il certificato è solo un po 'di ciclo hamiltoniano il cui peso è al massimo di C . Se si potesse risolvere questo problema in modo efficace, si potrebbe trovare il costo di un tour minimo ricerca binaria, a cominciare con il peso di tutta la rete come un limite superiore.

Answer 3

Probabilmente state pensando al problema di determinare se una data soluzione al TSP è la più soluzione. Tuttavia, non esiste una soluzione polinomiale noti per questo, il che significa che questo problema è in NP-hard, ma non necessariamente NP-completo.

Il TSP decisione Problema è in realtà su come determinare se il peso di una soluzione in un G grafico è al massimo C costo (come spiegato meglio nella risposta di Niel), che è certamente verificabili in tempo polinomiale.

Answer 4

E 'possibile dimostrare che è ottimale dato un oracolo che risolve il problema decisione (vedi altre risposte) in tempo polinomiale di interrogare se esiste una soluzione più breve. Se il vostro obiettivo è quello di costruire una soluzione ottimale dato l'oracolo, procedere come segue. Trovare il peso totale minimo tramite ricerca binaria (o se vi sono non interi pesi bordo, per un peso totale che differisce dal minimo di inferiore alla differenza min tra due pesi di bordo). Chiamare questo valore $ M $. Per ogni bordo nel grafico, rimuovere il bordo, e interrogare l'oracolo per vedere se v'è ancora una soluzione al massimo di $ M $. Se è così, lasciare il bordo, e continuare. In caso contrario, mettere il bordo posteriore in, e continuare. Quando hai elaborato tutti i bordi, ti verrà lasciato con un ciclo Hamiltoniano di peso minimo.