Nel caso migliore esecuzione in tempo per risolvere un problema NP-completo?

Question

Qual è l'algoritmo più veloce che esiste con per risolvere un particolare problema NP-completo? Ad esempio, un ingenuo attuazione di viaggia venditore è O (n!), Ma con la programmazione dinamica essa può essere fatto in O (n ^ 2 * 2 ^ n). C'è qualche "semplice" problema forse NP-completo che ha una migliore tempo di esecuzione?

Sono curioso di sapere soluzioni esatte, non approssimazioni.

Answer 1

  

[...] con la programmazione dinamica che può essere fatto in O (n ^ 2 * 2 ^ n). C'è qualche "semplice" problema forse NP-completo che ha una migliore tempo di esecuzione?

Un po '. Si può sbarazzarsi di qualsiasi fattore polinomiale creando un problema artificiale che codifica per la stessa soluzione in un ingresso polinomialmente più grande. Finché l'ingresso è soltanto polinomiale grande, il problema risultante è ancora NP-completo. Poiché la complessità è per definizione la funzione che mappa del formato per tempo di esecuzione, se la dimensione dell'input cresce la funzione ottiene in classi inferiori O.

Quindi, lo stesso algoritmo esecuzione sul TSP con l'ingresso imbottito con n ^ 2 bit inutili, avrà complessità O (1 * 2 ^ sqrt (n)).

Answer 2

Una caratteristica dei problemi NP-completi è che nessuno dei problemi NP possono essere trasformate meccanicamente in nessuno dei problemi NP-completi di, al massimo, tempo polinomiale.

Quindi, qualunque sia la soluzione migliore per un dato problema NP-completo è, è automaticamente un similmente-buona soluzione per qualsiasi altro problema NP.

Dato che la programmazione dinamica in grado di risolvere problema del commesso viaggiatore in 2 ^ tempo n e 2 ^ nr, lo stesso deve essere vero per tutti gli altri problemi NP [beh, più il tempo per applicare la trasformazione, immagino - in modo che possa essere di 2 ^ (n + 1)].

Answer 3

In genere non è possibile trovare il migliore soluzione per il problema del commesso viaggiatore generica senza provare tutte le combinazioni (ci potrebbe essere distanze negative, ecc).

Con l'aggiunta di ulteriori restrizioni e allentando il requisito di ottenere il migliore soluzione, è possibile accelerare le cose un bel po '.

Per esempio si può ottenere il tempo eseguibile polinomiale se le distanze nel problema obbediscono alla "non è più tempo per andare direttamente da A a B di andare da A a C a B" (cioè un collegamento non è mai più), < em> e si può vivere con il risultato massimo essere 1,5 volte il valore ottimale. Vedere http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP