Analogie tra Classe di complessità e EXPTIME
Classe di complessità e EXPTIME hanno 7 punti in comune (in Unionpedia): EXPSPACE, Macchina di Turing, NP (complessità), P (complessità), Problema decisionale, PSPACE, Teoria della complessità computazionale.
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.
Classe di complessità e EXPSPACE · EXPSPACE e EXPTIME ·
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.
Classe di complessità e Macchina di Turing · EXPTIME e Macchina di Turing ·
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.
Classe di complessità e NP (complessità) · EXPTIME e NP (complessità) ·
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Classe di complessità e P (complessità) · EXPTIME e P (complessità) ·
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.
Classe di complessità e Problema decisionale · EXPTIME e Problema decisionale ·
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.
Classe di complessità e PSPACE · EXPTIME e PSPACE ·
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.
Classe di complessità e Teoria della complessità computazionale · EXPTIME e Teoria della complessità computazionale ·
La lista di cui sopra risponde alle seguenti domande
- In quello che appare come Classe di complessità e EXPTIME
- Che cosa ha in comune Classe di complessità e EXPTIME
- Analogie tra Classe di complessità e EXPTIME
Confronto tra Classe di complessità e EXPTIME
Classe di complessità ha 23 relazioni, mentre EXPTIME ha 18. Come hanno in comune 7, l'indice di Jaccard è 17.07% = 7 / (23 + 18).
Riferimenti
Questo articolo mostra la relazione tra Classe di complessità e EXPTIME. Per accedere a ogni articolo dal quale è stato estratto informazioni, visitare: