l'accesso più veloce di browser!
11 relazioni: AC0, BQP (complessità), Calcolo distribuito, Classe di complessità, EXPSPACE, EXPTIME, Glossario delle classi di complessità, Macchina di Turing probabilistica, STRIPS, Teorema di Savitch, 2-EXPTIME.
AC0
AC0 è una classe di complessità usata nella complessità dei circuiti.
Nuovo!!: PSPACE e AC0 · Mostra di più »
BQP (complessità)
Nella teoria della complessità computazionale, BQP (Bounded-error Quantum Polynomial-time, "tempo polinomiale quantistico con errore limitato") è una classe di complessità a cui appartengono quei problemi che richiedono un tempo polinomiale da parte di un computer quantistico per avere una soluzione corretta con probabilità maggiore o uguale a 2/3 e quindi, corrispondentemente, con una probabilità di errore minore o uguale a 1/3.
Nuovo!!: PSPACE e BQP (complessità) · Mostra di più »
Calcolo distribuito
Il calcolo distribuito è un campo dell'informatica che studia i sistemi distribuiti.
Nuovo!!: PSPACE e Calcolo distribuito · Mostra di più »
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: PSPACE e Classe di complessità · Mostra di più »
EXPSPACE
Nella teoria della complessità, EXPSPACE è l'insieme di tutti i problemi di decisione risolvibili da una macchina deterministica di Turing nello spazio O(2p(n)), dove p(n) è una funzione polinomiale di n. (Alcuni autori restringono p(n) all'essere una funzione lineare, ma la maggior parte degli autori invece chiamano la classe risultante ESPACE.) Se usiamo invece una macchina non deterministica, otteniamo la classe NEXPSPACE, che è uguale a EXPSPACE per il teorema di Savitch.
Nuovo!!: PSPACE e EXPSPACE · 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!!: PSPACE e EXPTIME · Mostra di più »
Glossario delle classi di complessità
Questa pagina presenta un glossario delle classi di complessità, insiemi concernenti la teoria della complessità computazionale.
Nuovo!!: PSPACE e Glossario delle classi di complessità · Mostra di più »
Macchina di Turing probabilistica
Nella teoria della calcolabilità, una macchina di Turing probabilistica è una macchina di Turing non deterministica che sceglie a caso fra le transizioni disponibili in ogni fase secondo una determinata distribuzione di probabilità.
Nuovo!!: PSPACE e Macchina di Turing probabilistica · Mostra di più »
STRIPS
Nell'intelligenza artificiale, STRIPS (STanford Research Institute Problem Solver) è un pianificatore automatico sviluppato nel 1971 da Richard Fikes e Nils Nilsson dell'università di Stanford.
Nuovo!!: PSPACE e STRIPS · Mostra di più »
Teorema di Savitch
Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione f\left(n\right) \ge n: In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio.
Nuovo!!: PSPACE e Teorema di Savitch · 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!!: PSPACE e 2-EXPTIME · Mostra di più »
