Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

EXPSPACE

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

Indice

  1. 18 relazioni: Addizione, Algoritmo, Concatenazione, Espressione regolare, EXPTIME, Funzione lineare, Insieme, Macchina di Turing, Moltiplicazione, NP (complessità), Numero reale, O-grande, P (complessità), PSPACE, Star di Kleene, Teorema di Savitch, Teoria del primo ordine, Teoria della complessità computazionale.

  2. Classi di complessità

Addizione

Laddizione (denotata normalmente dal simbolo del più, "+") è una delle quattro operazioni fondamentali dell'aritmetica, insieme alla sottrazione, alla moltiplicazione e alla divisione.

Vedere EXPSPACE e Addizione

Algoritmo

In matematica e informatica un algoritmo è la specificazione di una sequenza finita di operazioni (dette anche istruzioni) che consente di risolvere tutti i quesiti di una stessa classe o di calcolare il risultato di un'espressione matematica.

Vedere EXPSPACE e Algoritmo

Concatenazione

La concatenazione è un elemento architettonico consistente in un'articolazione sulla parete muraria caratterizzata dal succedersi di interassi costanti scanditi dall'ordine architettonico, su paraste o semicolonne, al cui interno si apre un arco a tutto sesto o una serie di archi.

Vedere EXPSPACE e Concatenazione

Espressione regolare

Unespressione regolare (o, in forma abbreviata, regexp, regex o RE) è una sequenza di simboli (quindi una stringa) che identifica un insieme di stringhe.

Vedere EXPSPACE e Espressione regolare

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.

Vedere EXPSPACE e EXPTIME

Funzione lineare

In matematica, per funzione lineare si intende.

Vedere EXPSPACE e Funzione lineare

Insieme

In matematica, una collezione di elementi rappresenta un insieme se esiste un criterio oggettivo che permette di decidere univocamente se un qualunque elemento fa parte o no del raggruppamento.

Vedere EXPSPACE e Insieme

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.

Vedere EXPSPACE e Macchina di Turing

Moltiplicazione

La moltiplicazione è una delle quattro operazioni fondamentali dell'aritmetica. È un modo rapido per rappresentare la somma di numeri uguali.

Vedere EXPSPACE e Moltiplicazione

NP (complessità)

La classe di problemi N!P comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.

Vedere EXPSPACE e NP (complessità)

Numero reale

In matematica, i numeri reali possono essere descritti in maniera non formale come numeri ai quali è possibile attribuire uno sviluppo decimale finito o infinito, come pi.

Vedere EXPSPACE e Numero reale

O-grande

La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice, ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro.

Vedere EXPSPACE e O-grande

P (complessità)

Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.

Vedere EXPSPACE e P (complessità)

PSPACE

Nella teoria della complessità computazionale, la classe di problemi PSPACE, che sta per 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 input e k è un qualsiasi valore finito.

Vedere EXPSPACE e PSPACE

Star di Kleene

In logica matematica e in informatica, la stella di Kleene (o chiusura di Kleene, o operatore di Kleene) è un'operazione unaria definita su un insieme di stringhe o su un insieme di simboli o caratteri.

Vedere EXPSPACE e Star di Kleene

Teorema di Savitch

Nella teoria della complessità computazionale, il teorema di Savitch, dimostrato da Walter Savitch nel 1970, afferma che per ogni funzione fleft(nright) ge n: In altre parole, se una macchina di Turing non deterministica è in grado di risolvere un problema in spazio f(n), una macchina di Turing deterministica può risolvere lo stesso problema nel quadrato dello spazio.

Vedere EXPSPACE e Teorema di Savitch

Teoria del primo ordine

Nella logica matematica, una teoria del primo ordine (o calcolo dei predicati) è un particolare sistema formale, cioè una teoria formale, in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico.

Vedere EXPSPACE e Teoria del primo ordine

Teoria della complessità computazionale

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.

Vedere EXPSPACE e Teoria della complessità computazionale

Vedi anche

Classi di complessità