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. In termini di DSPACE e NSPACE, EXPSPACE = ⋃ k ∈ N DSPACE ( 2 n k ) = ⋃ k ∈ N NSPACE ( 2 n k ) {\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})} Un problema di decisione è EXPSPACE-completo se è in EXPSPACE, e ogni problema in EXPSPACE ha una riduzione di tempo polinomiale ad esso. In altre parole, c'è un algoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I problemi EXPSPACE-completi potrebbero essere pensati come i problemi più difficili in EXPSPACE. EXPSPACE è un superinsieme stretto di PSPACE, NP e P e si crede sia un superinsieme stretto di EXPTIME. Un esempio di un problema EXPSPACE-completo è quello di riconoscere se due espressioni regolari rappresentano linguaggi diversi, dove le espressioni sono limitate a quattro operatori: unione, concatenazione, la stella di Kleene (zero o più copie di un'espressione) e quadratura (due copie di un'espressione). Se si tralascia la stella di Kleene, allora quel problema diventa NEXPTIME-completo, che è come EXPTIME-completo, tranne che è definito in termini di macchine di Turing non deterministiche anziché deterministiche. È stato anche mostrato da L. Berman nel 1980 che il problema di verificare/falsificare una qualsiasi affermazione del primo ordine sui numeri reali che implichi soltanto l'addizione e il confronto (ma non la moltiplicazione) è in 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.
In termini di DSPACE e NSPACE,
Un problema di decisione è EXPSPACE-completo se è in EXPSPACE, e ogni problema in EXPSPACE ha una riduzione di tempo polinomiale ad esso. In altre parole, c'è un algoritmo di tempo polinomiale che trasforma richieste dell'uno in richieste dell'altro con la stessa risposta. I problemi EXPSPACE-completi potrebbero essere pensati come i problemi più difficili in EXPSPACE.
EXPSPACE è un superinsieme stretto di PSPACE, NP e P e si crede sia un superinsieme stretto di EXPTIME.
Un esempio di un problema EXPSPACE-completo è quello di riconoscere se due espressioni regolari rappresentano linguaggi diversi, dove le espressioni sono limitate a quattro operatori: unione, concatenazione, la stella di Kleene (zero o più copie di un'espressione) e quadratura (due copie di un'espressione).[1]
Se si tralascia la stella di Kleene, allora quel problema diventa NEXPTIME-completo, che è come EXPTIME-completo, tranne che è definito in termini di macchine di Turing non deterministiche anziché deterministiche.
È stato anche mostrato da L. Berman nel 1980 che il problema di verificare/falsificare una qualsiasi affermazione del primo ordine sui numeri reali che implichi soltanto l'addizione e il confronto (ma non la moltiplicazione) è in EXPSPACE.
Note
[modifica | modifica wikitesto]- ^ Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.
Bibliografia
[modifica | modifica wikitesto]- L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Sezione 9.1.1: "Exponential space completeness", pp. 313–317. Dimostra che determinare l'equivalenza delle espressioni regolari con l'esponenziazione è EXPSPACE-completo.
