Indice
9 relazioni: Algoritmo Monte Carlo, BPP (complessità), Complessità temporale, Completo (complessità), Lista delle classi di complessità, Macchina di Turing probabilistica, Problema della cricca, RP (complessità), Test di primalità.
Algoritmo Monte Carlo
Per algoritmo Monte Carlo si intende un algoritmo randomizzato il cui output può essere sbagliato in un certo numero - solitamente ridotto - di casi.
Vedere ZPP (complessità) e Algoritmo Monte Carlo
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.
Vedere ZPP (complessità) e BPP (complessità)
Complessità temporale
In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.
Vedere ZPP (complessità) e Complessità temporale
Completo (complessità)
Nella teoria della complessità computazionale, un problema computazionale è completo per una classe di complessità se è, in senso tecnico, tra i problemi "più difficili" (o "più espressivi") di quella classe.
Vedere ZPP (complessità) e Completo (complessità)
Lista delle classi di complessità
Questa pagina contiene la lista delle classi di complessità, insiemi concernenti la teoria della complessità computazionale. Nell'articolo computazione compare una mappa delle relazioni di inclusione dimostrabili per le classi di complessità.
Vedere ZPP (complessità) e Lista delle classi di complessità
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à.
Vedere ZPP (complessità) e Macchina di Turing probabilistica
Problema della cricca
In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.
Vedere ZPP (complessità) e Problema della cricca
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.
Vedere ZPP (complessità) e RP (complessità)
Test di primalità
Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero: quest'ultima operazione è infatti generalmente più lunga e complessa.