l'accesso più veloce di browser!
14 relazioni: BPP (complessità), BQP, Classe di complessità, Complemento (complessità), Computer quantistico, Disuguaglianza di Markov, EXPTIME, Macchina di Turing, Macchina di Turing probabilistica, P (complessità), RP (complessità), Scott Aaronson, Teoria della complessità computazionale, Valore atteso.
BPP (complessità)
Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta.
Nuovo!!: ZPP (complessità) e BPP (complessità) · Mostra di più »
BQP
Nessuna descrizione.
Nuovo!!: ZPP (complessità) e BQP · Mostra di più »
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: ZPP (complessità) e Classe di complessità · Mostra di più »
Complemento (complessità)
Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no.
Nuovo!!: ZPP (complessità) e Complemento (complessità) · Mostra di più »
Computer quantistico
Un computer quantistico (o quantico) è un nuovo dispositivo per il trattamento ed elaborazione delle informazioni che, per eseguire le classiche operazioni sui dati, utilizza i fenomeni tipici della meccanica quantistica, come la sovrapposizione degli effetti e l'entanglement.
Nuovo!!: ZPP (complessità) e Computer quantistico · Mostra di più »
Disuguaglianza di Markov
In teoria della probabilità e statistica, la disuguaglianza di Markov afferma che, per una variabile casuale \ X non negativa il cui valore atteso esiste: Questa disuguaglianza permette di stabilire un limite superiore al valore di probabilità dalla sola conoscenza del valore atteso E, a condizione che la variabile casuale sia definita non negativa.
Nuovo!!: ZPP (complessità) e Disuguaglianza di Markov · 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!!: ZPP (complessità) e EXPTIME · Mostra di più »
Macchina di Turing
In informatica una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.
Nuovo!!: ZPP (complessità) e Macchina di Turing · 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!!: ZPP (complessità) e Macchina di Turing probabilistica · 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!!: ZPP (complessità) e P (complessità) · Mostra di più »
RP (complessità)
Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.
Nuovo!!: ZPP (complessità) e RP (complessità) · Mostra di più »
Scott Aaronson
Dopo la laurea in informatica alla Cornell University nel 2000, dal sito web di Aaronson.
Nuovo!!: ZPP (complessità) e Scott Aaronson · 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!!: ZPP (complessità) e Teoria della complessità computazionale · Mostra di più »
Valore atteso
In teoria della probabilità il valore atteso (chiamato anche media, speranza o speranza matematica) di una variabile casuale X, è un numero indicato con \mathbb (da expected value o expectation in inglese o dal francese espérance) che formalizza l'idea euristica di valore medio di un fenomeno aleatorio.
Nuovo!!: ZPP (complessità) e Valore atteso · Mostra di più »
