l'accesso più veloce di browser!
5 relazioni: Classe di complessità, EXPTIME, P (complessità), Teoria della complessità computazionale, 2-EXPTIME.
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: Gerarchia esponenziale e Classe di complessità · Mostra di più »
EXPTIME
Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette.
Nuovo!!: Gerarchia esponenziale e EXPTIME · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: Gerarchia esponenziale e P (complessità) · Mostra di più »
Teoria della complessità computazionale
In informatica, la teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.
Nuovo!!: Gerarchia esponenziale e Teoria della complessità computazionale · Mostra di più »
2-EXPTIME
Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(22p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che 2-EXPTIME può anche essere riformulato come la classe di spazio AEXPSPACE, i problemi che possono essere risolti da una macchina di Turing alternante in spazio esponenziale.
Nuovo!!: Gerarchia esponenziale e 2-EXPTIME · Mostra di più »
