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

EXPTIME

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

18 relazioni: Algoritmo, Classe di complessità, Computabilità, Dama, EXPSPACE, Gerarchia esponenziale, Go (gioco), Insieme, Macchina di Turing, Matrice delle adiacenze, NP (complessità), O-grande, P (complessità), Problema decisionale, PSPACE, Scacchi, Teoria della complessità computazionale, 2-EXPTIME.

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.

Nuovo!!: EXPTIME e Algoritmo · Mostra di più »

Classe di complessità

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

Nuovo!!: EXPTIME e Classe di complessità · Mostra di più »

Computabilità

La teoria della computabilità effettiva si occupa della esistenza o meno di algoritmi risolutivi di problemi.

Nuovo!!: EXPTIME e Computabilità · Mostra di più »

Dama

La dama è un gioco da tavolo tradizionale per due giocatori.

Nuovo!!: EXPTIME e Dama · 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!!: EXPTIME e EXPSPACE · 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!!: EXPTIME e Gerarchia esponenziale · Mostra di più »

Go (gioco)

Il go è un gioco da tavolo strategico per due giocatori.

Nuovo!!: EXPTIME e Go (gioco) · Mostra di più »

Insieme

In matematica, un raggruppamento di oggetti rappresenta un insieme se esiste un criterio oggettivo che permette di decidere univocamente se un qualunque oggetto fa parte o no del raggruppamento.

Nuovo!!: EXPTIME e Insieme · 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!!: EXPTIME e Macchina di Turing · Mostra di più »

Matrice delle adiacenze

La matrice delle adiacenze o matrice di connessione costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi.

Nuovo!!: EXPTIME e Matrice delle adiacenze · 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!!: EXPTIME e NP (complessità) · Mostra di più »

O-grande

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

Nuovo!!: EXPTIME e O-grande · 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!!: EXPTIME 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!!: EXPTIME 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!!: EXPTIME e PSPACE · Mostra di più »

Scacchi

Gli scacchi sono un gioco da tavolo di strategia che vede opposti due avversari, detti Bianco o Nero secondo il colore dei pezzi che muovono.

Nuovo!!: EXPTIME e Scacchi · 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!!: EXPTIME e Teoria della complessità computazionale · 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!!: EXPTIME e 2-EXPTIME · Mostra di più »

Riorienta qui:

EXP.

UscenteArrivo
Ehi! Siamo su Facebook ora! »