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

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

7 relazioni: Classe di complessità, EXPTIME, Macchina di Turing, O-grande, Problema decisionale, Scott Aaronson, Teoria della complessità computazionale.

Classe di complessità

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

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

O-grande

La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni.

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

Scott Aaronson

Dopo la laurea in informatica alla Cornell University nel 2000, dal sito web di Aaronson.

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

UscenteArrivo
Ehi! Siamo su Facebook ora! »