l'accesso più veloce di browser!
23 relazioni: BPP (complessità), BQP, Co-NP, EXPSPACE, EXPTIME, Glossario delle classi di complessità, Inclusione, Linguaggio dipendente dal contesto, Linguaggio libero dal contesto, Linguaggio regolare, Linguaggio ricorsivamente enumerabile, Linguaggio ricorsivo, Logica matematica, Macchina astratta, Macchina di Turing, NC (complessità), NP (complessità), NP-completo, P (complessità), Problema decisionale, PSPACE, Teoria della calcolabilità, Teoria della complessità computazionale.
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ù »
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ù »
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!!: Classe di complessità 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!!: Classe di complessità 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!!: Classe di complessità e Glossario delle classi di complessità · 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!!: Classe di complessità e Inclusione · Mostra di più »
Linguaggio dipendente dal contesto
Un linguaggio dipendente dal contesto (o anche sensibile al contesto, vincolato al contesto, o contestuale) è un linguaggio formale che può essere definito da una grammatica dipendente dal contesto.
Nuovo!!: Classe di complessità e Linguaggio dipendente dal contesto · Mostra di più »
Linguaggio libero dal contesto
Un linguaggio libero dal contesto (o non contestuale, o context-free) è un linguaggio formale generato da una grammatica che sia, appunto, non contestuale, ovvero tale che le cui regole agiscono su simboli non terminali a prescindere dal contesto in cui essi appaiono.
Nuovo!!: Classe di complessità e Linguaggio libero dal contesto · Mostra di più »
Linguaggio regolare
In informatica teorica un linguaggio regolare è un linguaggio formale, ossia costituito da un insieme di stringhe costruite con un alfabeto finito, che è descritto da un'espressione regolare, generato da una grammatica generativa regolare (o di tipo 3, secondo la gerarchia di Chomsky) o accettato da un automa a stati finiti (automa a stati finiti deterministico o automa a stati finiti non deterministico).
Nuovo!!: Classe di complessità e Linguaggio regolare · Mostra di più »
Linguaggio ricorsivamente enumerabile
Un insieme A è detto ricorsivamente enumerabile quando esiste una funzione di enumerazione f di cui A è il codominio.
Nuovo!!: Classe di complessità e Linguaggio ricorsivamente enumerabile · Mostra di più »
Linguaggio ricorsivo
In matematica, logica e informatica teorica, i linguaggi decidibili o ricorsivi sono una classe di linguaggi formali che corrisponde alla classe dei problemi decidibili.
Nuovo!!: Classe di complessità e Linguaggio ricorsivo · Mostra di più »
Logica matematica
La logica matematica è il settore della matematica che studia i sistemi formali dal punto di vista del modo di codificare i concetti intuitivi della dimostrazione e di computazione come parte dei fondamenti della matematica.
Nuovo!!: Classe di complessità e Logica matematica · Mostra di più »
Macchina astratta
In informatica il termine macchina astratta indica un modello teorico di hardware o software, in grado di eseguire operazioni, memorizzarne il risultato e seguire il flusso dell'algoritmo.
Nuovo!!: Classe di complessità e Macchina astratta · 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!!: Classe di complessità e Macchina di Turing · 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ù »
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ù »
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ù »
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!!: Classe di complessità e Problema decisionale · Mostra di più »
PSPACE
Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di O(n^k), dove n è la dimensione dei dati di ingresso e k è un qualsiasi valore finito.
Nuovo!!: Classe di complessità e PSPACE · Mostra di più »
Teoria della calcolabilità
La teoria della calcolabilità, della computabilità, e della ricorsione cerca di comprendere quali funzioni possono essere calcolate tramite un procedimento automatico.
Nuovo!!: Classe di complessità e Teoria della calcolabilità · 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ù »
