l'accesso più veloce di browser!
47 relazioni: AC (complessità), AC0, AM, BPP, BPP (complessità), BQP, BQP (complessità), Classi di complessità P e NP, Co-NP, Complemento (complessità), Complessità dei circuiti, Complessità temporale, Completo (complessità), Componente connessa (teoria dei grafi), DLOGTIME, E (complessità), E (disambigua), EXPTIME, FNP, Funzione unidirezionale, Gerarchia esponenziale, Glossario delle classi di complessità, L (complessità), L (disambigua), NC (complessità), NL, NL (complessità), NP, NP (complessità), NP-completo, Numero primo, P (complessità), PPT, Problema del commesso viaggiatore, Problema di funzione, RE, RP, RP (complessità), Sharp-P, Sharp-P-completo, Soddisfacibilità booleana, Teorema dello speedup di Blum, Teoria della complessità computazionale, UP, ZPP, ZPP (complessità), 2-EXPTIME.
AC (complessità)
Nella complessità dei circuiti, AC è una gerarchia di classi di complessità.
Nuovo!!: Classe di complessità e AC (complessità) · Mostra di più »
AC0
AC0 è una classe di complessità usata nella complessità dei circuiti.
Nuovo!!: Classe di complessità e AC0 · Mostra di più »
AM
Nessuna descrizione.
Nuovo!!: Classe di complessità e AM · Mostra di più »
BPP
Nessuna descrizione.
Nuovo!!: Classe di complessità e BPP · Mostra di più »
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!!: Classe di complessità e BPP (complessità) · Mostra di più »
BQP
Nessuna descrizione.
Nuovo!!: Classe di complessità e BQP · 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!!: Classe di complessità e BQP (complessità) · Mostra di più »
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.
Nuovo!!: Classe di complessità e Classi di complessità P e NP · Mostra di più »
Co-NP
Nella teoria della complessità computazionale, coNP è la classe di problemi complementari a quelli della classe NP.
Nuovo!!: Classe di complessità e Co-NP · 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!!: Classe di complessità e Complemento (complessità) · Mostra di più »
Complessità dei circuiti
In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano.
Nuovo!!: Classe di complessità e Complessità dei circuiti · 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!!: Classe di complessità e Complessità temporale · Mostra di più »
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.
Nuovo!!: Classe di complessità e Completo (complessità) · Mostra di più »
Componente connessa (teoria dei grafi)
Nella teoria dei grafi, una componente connessa (o semplicemente una componente) di un grafo indiretto è un sottografo in cui.
Nuovo!!: Classe di complessità e Componente connessa (teoria dei grafi) · Mostra di più »
DLOGTIME
Nella teoria della complessità computazionale DLOGTIME è la classe di complessità di tutti i problemi computazionali risolvibili in una quantità logaritmica di tempo computazionale da una macchina di Turing deterministica.
Nuovo!!: Classe di complessità e DLOGTIME · 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!!: Classe di complessità e E (complessità) · Mostra di più »
E (disambigua)
*E – quinta lettera dell'alfabeto italiano.
Nuovo!!: Classe di complessità e E (disambigua) · 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!!: Classe di complessità e EXPTIME · Mostra di più »
FNP
Nessuna descrizione.
Nuovo!!: Classe di complessità e FNP · Mostra di più »
Funzione unidirezionale
Una funzione unidirezionale (funzione one-way in inglese) è una funzione matematica "facile da calcolare" ma "difficile da invertire".
Nuovo!!: Classe di complessità e Funzione unidirezionale · Mostra di più »
Gerarchia esponenziale
Nella teoria della complessità computazionale, la gerarchia esponenziale è una gerachia di classi di complessità, che inizia con EXPTIME: e continua con e così via.
Nuovo!!: Classe di complessità e Gerarchia esponenziale · 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!!: Classe di complessità e Glossario delle classi di complessità · Mostra di più »
L (complessità)
Nella teoria della complessità computazionale, L è la classe di complessità che contiene i problemi di decisione che possono essere risolti da una macchina di Turing deterministica usando una quantità logaritmica di memoria.
Nuovo!!: Classe di complessità e L (complessità) · Mostra di più »
L (disambigua)
L è la decima lettera dell'alfabeto italiano.
Nuovo!!: Classe di complessità e L (disambigua) · Mostra di più »
NC (complessità)
Nella teoria della complessità i problemi NC sono i problemi efficientemente parallelizzabili cioè che possono essere risolti in tempo polilogaritmico avendo a disposizione una quantità di hardware polinomiale rispetto alla dimensione dell'input.
Nuovo!!: Classe di complessità e NC (complessità) · Mostra di più »
NL
Nessuna descrizione.
Nuovo!!: Classe di complessità e NL · Mostra di più »
NL (complessità)
La classe NL è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con S_M(n).
Nuovo!!: Classe di complessità e NL (complessità) · Mostra di più »
NP
Nessuna descrizione.
Nuovo!!: Classe di complessità e NP · 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!!: Classe di 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!!: Classe di complessità e NP-completo · 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!!: Classe di complessità e Numero primo · 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!!: Classe di complessità e P (complessità) · Mostra di più »
PPT
Nessuna descrizione.
Nuovo!!: Classe di complessità e PPT · Mostra di più »
Problema del commesso viaggiatore
Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling.
Nuovo!!: Classe di complessità e Problema del commesso viaggiatore · Mostra di più »
Problema di funzione
Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO".
Nuovo!!: Classe di complessità e Problema di funzione · Mostra di più »
RE
Nessuna descrizione.
Nuovo!!: Classe di complessità e RE · Mostra di più »
RP
Nessuna descrizione.
Nuovo!!: Classe di complessità e RP · 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!!: Classe di complessità e RP (complessità) · Mostra di più »
Sharp-P
Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP.
Nuovo!!: Classe di complessità e Sharp-P · Mostra di più »
Sharp-P-completo
#P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale.
Nuovo!!: Classe di complessità e Sharp-P-completo · Mostra di più »
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Nuovo!!: Classe di complessità e Soddisfacibilità booleana · Mostra di più »
Teorema dello speedup di Blum
Nella teoria della complessità computazionale, il Teorema dello speedup di Blum, proposto da Manuel Blum nel 1967, è un importante teorema dello speedup riguardante la complessità delle funzioni calcolabili.
Nuovo!!: Classe di complessità e Teorema dello speedup di Blum · 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!!: Classe di complessità e Teoria della complessità computazionale · Mostra di più »
UP
Nessuna descrizione.
Nuovo!!: Classe di complessità e UP · Mostra di più »
ZPP
Nessuna descrizione.
Nuovo!!: Classe di complessità e ZPP · 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!!: Classe di complessità e ZPP (complessità) · 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!!: Classe di complessità e 2-EXPTIME · Mostra di più »
