Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 18.Space Complexity


Definizione Space-complexity

Definizione: Sia M un macchina di Turing deterministica che si ferma su tutti gli input. La complessità di spazio (space complexity) di M è la funzione f: N→N, dove f(n) è il massimo numero di celle del nastro che M legge su un input di lunghezza n. Se la complessità di spazio di M è f(n), allora diremo che M lavora in spazio f(n).

Se M è una macchina di Turing non deterministica dove tutti i rami della computazione si fermano su tutti i possibili input, definiamo la sua complessità di spazio f(n) come il massimo numero di celle del nastro che M vede su tutti i rami della computazione per un input di lunghezza n.

Space e NSpace

Definizione: Sia f: NR+ una funzione. Le classi di complessità di spazio SPACE(f(n)) e NSPACE((f(n)) sono definite come segue:

  • SPACE((f(n)) = {L | L è un linguaggio deciso da una macchina di Turing deterministica in spazio O(f(n))}.
  • NSPACE(f(n)) = {L | L è un linguaggio deciso da una macchina di Turing non deterministica in spazio O(f(n))}.

Lo Spazio è più potente del Tempo – Esempio

Esempio 1: SAT è spazio-lineare!
Sappiamo che il problema SAT è NP-completo, e che quindi non può essere risolto con una MdT deterministica in tempo polinomiale.
Lo spazio ha però una caratteristica vincente rispetto al tempo: può essere riutilizzato!
L’idea per la nostra MdT che risolve il problema SAT in spazio lineare, è quella di assegnare una cella ad ogni variabile, e riutilizzarla ogni volta che facciamo un nuovo assegnamento:

M = “Su input <φ>, dove φ è una formula booleana con m variabili:

  1. Per ciascun assegnamento vero delle variabili x1,…xm di φ
  2. Valuta φ su queste assegnazioni di verità
  3. Se φ viene valutata 1, accept, altrimenti reject. “

Ogni iterazione del loop richiede solo memoria aggiuntiva per ricor-dare l’assegnamento corrente di verità e per valutare il valore di φ.
Tutto ciò richiede spazio O(n). Questo spazio può essere riciclato alla successiva iterazione. Così, la complessità di spazio di questo algoritmo rimane lineare.

Not ALL è spazio lineare – Esempio

Sia ALLNFA, il linguaggio degli automi che accettano tutte le stringhe su un dato alfabeto. Formalmente, ALLNFA = { | A è un NFA ed L(A)=Σ*}
Sia Comp(ALLNFA) il complemento di ALLNFA.
Comp(ALLNFA) è accettato da una MdT nondeterministica in spazio lineare.
Intuitivamente, il non determinismo è usato per trovare una stringa che sia rifiutata dall’NFA.
Una quantità di spazio lineare nel numero degli stati dell’automa sotto esame è sufficiente a tenere traccia degli stati in cui l’automa può trovarsi in un determinato momento.
Si ricordi che ad ogni istante, un automa nondeterministico con Q stati può essere in un insieme di stati pari a 2Q.

Not ALL è spazio lineare – Esempio

Formalmente la MdT N che risolve in spazio lineare Comp(ALLNFA) è la seguente:
N = “su ingresso <M> : (dove <M> è un NFA)
Si marca lo stato iniziale dell’NFA;
Per 2Q volte (dove Q è il numero di stati di M): Si seleziona in modo non deteriministico un simbolo d’ingresso e aggiorno le posizioni del marcatore sugli stati di M;
Se tutti i marcatori non vedono uno stato di accettazione, allora accept; altrimenti reject.”

Si noti che ogni iterazione del passo 2 non fa altro che simulare la lettura del simbolo selezionato in modo non deterministico.
Per costruzione di N, si ha necessità solo di spazio lineare per memorizzare le posizioni dei marcatori e per il contatore del ciclo descritto al passo 2. Spazio che ad ogni iterazione del ciclo è possibile riutilizzare.
Si noti che al momento non si sa se Comp(ALLNFA) è in NP e neppure in Co-NP.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion