Wiki definisce Tempo polinomiale come incolto:
Si dice che un algoritmo è di tempo polinomiale se il suo tempo di esecuzione è delimitato in alto da un espressione polinomiale in la dimensione dellinput per lalgoritmo, cioè $ T (n) = O (n ^ k) $ per qualche costante $ k $
I capire che in generale la differenza tra tempo polinomiale e tempo esponenziale è che la funzione esponenziale cresce strettamente più velocemente di qualsiasi funzione polinomiale, in modo asintotico ( riferimento ).
Sto cercando di capire il nucleo definizione di Tempo esponenziale .
- Quali elementi faranno funzionare un algoritmo in Tempo esponenziale ?
- Quale modifica devo fare nell espressione polinomiale per renderlo Tempo esponenziale ? (Con esso mi riferisco alla definizione dellalgoritmo allinizio della domanda)
Commenti
- 1. Fai molte cose in modo esponenziale. 2. Utilizza il polinomio come potenza di una base > 1.
- Non ' non capisco il tuo secondo domanda. I polinomi sono polinomi; gli esponenziali sono esponenziali. Chiedere cosa è necessario modificare per trasformare un polinomio in un esponenziale è come chiedere cosa è necessario modificare per trasformare un logaritmo in un coseno.
- @DavidRicherby Ci saranno funzioni temporali esponenziali se P = NP? Come si può definire una funzione tempo esponenziale in termini di espressione polinomiale?
- Le funzioni esponenziali esisteranno sicuramente ancora se P = NP. Probabilmente ci sono ancora problemi che ' impiegheranno un tempo esponenziale anche se P = NP, sebbene nessuno venga in mente immediatamente. Una funzione esponenziale può essere definita in termini di polinomio, ma quel polinomio deve essere infinitamente lungo: potresti cercare le espansioni di Taylor se ' sei interessato a questo.
- @ymbirtt Anche la versione più semplice del teorema della gerarchia temporale dice che non esiste un algoritmo tempo polinomiale per nessun problema di EXPTIME-complete. Questo ' è un risultato incondizionato: non ' non dipende dal presupposto che P $ \ neq $ NP.
Risposta
-
Non cè una risposta facile per questa, anche se ci sono segnali a cui prestare attenzione . Lesame di ogni possibile sottoinsieme di un insieme, ad esempio, è esponenziale, quindi se avessi un insieme di numeri interi $ \ {x_1, …, x_n \} $ e volessi controllare ogni sottoinsieme di questi per vedere se si sommano a $ 0 $, dovrei considerare esattamente $ 2 ^ n $ sottoinsiemi, il che rende il tempo esponenziale di questo metodo. Tuttavia, diverse trappole possono rendere esponenziale il tempo di un algoritmo, quindi invece di cercare ampie categorie, analizza gli algoritmi caso per caso.
-
Se un algoritmo richiede $ n ^ 2 $ passaggi per essere completato, allora è polinomiale. Se richiede $ 2 ^ n $ passaggi, è esponenziale. La differenza è la posizione di $ n $. Se qualcosa è $ O (n ^ m) $ per $ n > 1 $, $ m > 0 $, allora “s polinomio in $ n $ per $ m $ fissi, ma esponenziale in $ m $ per $ n $ fissi.
Commenti
- Attenzione. La funzione $ n ^ m $ non è ' t polinomio in $ n $ a meno che $ m $ non sia una costante. E, se $ m $ è una costante, ' non ha senso dire che la funzione è esponenziale in quella costante.
- Sì, tu ' ho ragione. ' lo chiarirò.
Risposta
Spesso si ottiene un algoritmo di forza bruta del tempo esponenziale quando si considera un problema e si enumera lintero spazio di ricerca. In genere, si “penseresti a problemi di sottoinsieme (in SAT, sceglieresti un sottoinsieme di variabili impostate su true), problemi di permutazione (in TSP, ogni tour è una permutazione delle città) e problemi di partizione (nella colorazione del grafico, stai cercando di p artizione dei vertici in classi di colore). Oppure considera lordinamento pari: ci sono $ n! $ Permutazioni di $ n $ interi. Passa attraverso ogni permutazione e controlla se è ordinato. Sciocco (e lento), ma funziona.
Commenti
- Anche se si noti che $ O (n!) $ È anche peggio di $ O ( k ^ n) $. Se ' stai ancora cercando di conoscere la complessità del tempo, questa potrebbe essere una cosa utile da dimostrare a te stesso.