Logo
Unionpedia
Comunicazione
Disponibile su Google Play
Nuovo! Scarica Unionpedia sul tuo dispositivo Android™!
Gratuito
l'accesso più veloce di browser!
 

BPP (complessità)

Indice 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.

29 relazioni: Algoritmo AKS, BQP (complessità), Circuito booleano, Classe di complessità, Complemento (complessità), Complessità temporale, Computer quantistico, Congettura, Costante matematica, Decadimento esponenziale, E (complessità), EXPTIME, Inclusione, Informatica, Leonard Adleman, Macchina di Turing, Macchina di Turing probabilistica, NP (complessità), NP-completo, Numeri pseudo-casuali, Numero primo, Oracolo random, P (complessità), Probabilità, Problema decisionale, RP (complessità), Simon Fraser University, Teoria della complessità computazionale, ZPP (complessità).

Algoritmo AKS

L'algoritmo AKS (dalle iniziali dei tre ideatori, i matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena) è un test di primalità di complessità polinomiale.

Nuovo!!: BPP (complessità) e Algoritmo AKS · 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!!: BPP (complessità) e BQP (complessità) · Mostra di più »

Circuito booleano

Un circuito booleano è un modello matematico di computazione usato nello studio della teoria della complessità computazionale.

Nuovo!!: BPP (complessità) e Circuito booleano · Mostra di più »

Classe di complessità

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.

Nuovo!!: BPP (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!!: BPP (complessità) e Complemento (complessità) · Mostra di più »

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.

Nuovo!!: BPP (complessità) e Complessità temporale · 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!!: BPP (complessità) e Computer quantistico · Mostra di più »

Congettura

Una congettura (dal latino coniectūra, dal verbo conīcere, ossia "interpretare, dedurre, concludere") è un'affermazione o un giudizio fondato sull'intuito, ritenuto probabilmente vero, ma non dimostrato, cioè dunque un'ipotesi.

Nuovo!!: BPP (complessità) e Congettura · Mostra di più »

Costante matematica

Le costanti matematiche sono quantità, solitamente numeri reali o complessi, che hanno un valore ben definito, a differenza delle variabili che possono assumere un valore non determinato a priori.

Nuovo!!: BPP (complessità) e Costante matematica · Mostra di più »

Decadimento esponenziale

In fisica e matematica, il decadimento esponenziale è la diminuzione di una quantità proporzionale al valore della stessa.

Nuovo!!: BPP (complessità) e Decadimento esponenziale · Mostra di più »

E (complessità)

Nella teoria della complessità computazionale, la classe di complessità E è l'insieme di problemi decisionali che possono essere risolti da una macchina deterministica di Turing nel tempo 2O(n) ed è perciò uguale alla classe di complessità DTIME(2O(n)).

Nuovo!!: BPP (complessità) e E (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!!: BPP (complessità) e EXPTIME · Mostra di più »

Inclusione

In matematica, e in particolare in teoria degli insiemi, l'inclusione, indicata con \subseteq, è una relazione binaria tra insiemi definita nel seguente modo: "l'insieme B è contenuto o incluso nell'insieme A se e solo se, per ogni elemento x, se x appartiene a B allora x appartiene ad A".

Nuovo!!: BPP (complessità) e Inclusione · Mostra di più »

Informatica

L'informatica è la scienza applicata che si occupa del trattamento dell'informazione mediante procedure automatizzate.

Nuovo!!: BPP (complessità) e Informatica · Mostra di più »

Leonard Adleman

Ha contribuito nel 1978 con Ronald Rivest e Adi Shamir allo sviluppo del sistema di crittografia asimmetrica RSA che infatti è un acronimo costituito dalle iniziali dei cognomi dei tre creatori: Ron Rivest, Adi Shamir, e Leonard Adleman.

Nuovo!!: BPP (complessità) e Leonard Adleman · 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!!: BPP (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!!: BPP (complessità) e Macchina di Turing probabilistica · Mostra di più »

NP (complessità)

La classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.

Nuovo!!: BPP (complessità) e NP (complessità) · Mostra di più »

NP-completo

Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.

Nuovo!!: BPP (complessità) e NP-completo · Mostra di più »

Numeri pseudo-casuali

Sono detti numeri pseudo-casuali (in inglese pseudo-random numbers) i numeri generati da un algoritmo deterministico che produce una sequenza con, approssimativamente, le stesse proprietà statistiche di una sequenza di numeri generata da un processo casuale.

Nuovo!!: BPP (complessità) e Numeri pseudo-casuali · Mostra di più »

Numero primo

In matematica, un numero primo (in breve anche primo) è un numero intero positivo che abbia esattamente due divisori distinti.

Nuovo!!: BPP (complessità) e Numero primo · Mostra di più »

Oracolo random

In crittografia, un oracolo random è una macchina a oracolo, una scatola nera teorica che risponde ad ogni domanda con una risposta veramente random scelta uniformemente all'interno del suo dominio di output.

Nuovo!!: BPP (complessità) e Oracolo random · 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!!: BPP (complessità) e P (complessità) · Mostra di più »

Probabilità

Il concetto di probabilità, utilizzato a partire dal XVII secolo, è diventato con il passare del tempo la base di diverse discipline scientifiche rimanendo tuttavia non univoco.

Nuovo!!: BPP (complessità) e Probabilità · Mostra di più »

Problema decisionale

Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri.

Nuovo!!: BPP (complessità) e Problema decisionale · 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!!: BPP (complessità) e RP (complessità) · Mostra di più »

Simon Fraser University

La Simon Fraser University (SFU) è un'università pubblica canadese situata nella Columbia Britannica, con campus a Burnaby, Vancouver e Surrey.

Nuovo!!: BPP (complessità) e Simon Fraser University · 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!!: BPP (complessità) e Teoria della complessità computazionale · Mostra di più »

ZPP (complessità)

Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà.

Nuovo!!: BPP (complessità) e ZPP (complessità) · Mostra di più »

UscenteArrivo
Ehi! Siamo su Facebook ora! »