• Autore:   Elia Argentieri
  • Ultima modifica:   6 mag 2022 18:07
  • Redazione:   2 feb 2022 19:50
  • Sorgente di questa pagina
  • Tempo di lettura:   8 minuti

Quando non sappiamo come risolvere un problema c’è un algoritmo che funziona sempre benissimo, se non per la sua complessità: l’algoritmo “a forza bruta”. Questo algoritmo origina un albero di scelte in cui i nodi interni rappresentano una computazione non ancora terminata e le foglie rappresentano una possibile soluzione del problema. Vengono esaminate tutte le possibili scelte, mossa che ha un costo esponenziale nella taglia dell’input.

In alternativa c’è un altro algoritmo, chiamato guess-and-try, che ci permette di evitare di esaminare sistematicamente tutte le possibili scelte, “lanciando un dado” di fronte ad ogni scelta. L’algoritmo esegue una successione di scelte casuali finché non viene raggiunta una foglia. Se questa soddisfa i requisiti del problema l’algoritmo accetta la soluzione. Visto che si tratta di un procedimento stocastico, potrebbe accadere che l’algoritmo selezioni casualmente la soluzione al primo tentativo oppure potrebbe ridursi al caso precedente, andando a controllare tutto l’albero. Tuttavia possiamo calcolare la probabilità che l’algoritmo termini entro un certo numero di tentativi e, se ritenuta sufficientemente bassa, questo metodo può rivelarsi una buona alternativa pratica al metodo di forza bruta.

Però quel che ci interessa di più, è il poter usare una MdT deterministica per visitare l’albero delle scelte dell’algoritmo guess-and-try. La visita deve avvenire livello per livello per garantire di trovare la soluzione (se procedessimo in profondità potremmo incappare in una computazione non terminante e non trovare mai nessuna soluzione).

Torniamo a parlare di Macchine di Turing non deterministiche. Le MdT non deterministiche generano un albero di possibili computazioni, come l’algoritmo guess-and-try, e si arrestano appena trovano una foglia che rappresenta una soluzione accettabile per il problema. Una MdT deterministica può simulare una MdT non deterministica, usando lo stesso algoritmo che consente alla MdT deterministica di simulare il guess-and-try. Questo significa che la MdT non deterministica può calcolare tutte e sole le stesse funzioni che calcola una MdT deterministica. Tuttavia la simulazione di una MdT non deterministica con una deterministica ci porta a perdere efficienza esponenzialmente, in quanto il numero di nodi di un albero cresce esponenzialmente rispetto alla sua profondità.

Macchine di Turing non deterministiche

Definizione: una MdT non deterministica è una tupla \(N = (Q, \Sigma, \delta, q_0, h)\) dove:

  • \(Q, \Sigma, q_0\) sono come nella definizione della versione deterministica
  • \(\Sigma \subseteq (Q \times \Sigma) \times ((Q \cup \{SI,NO\}) \times \Sigma \times \{L,R,-\})\) è la relazione di transizione.

Tale definizione può essere ovviamente adattata alle varie varianti come le macchine a k nastri e I/O.

Le computazioni sono sempre una successione di passi di computazione, esattamente come nella variante deterministica. Quel che accade di vermente diverso è che la macchina esamina contemporaneamente tutti le possibili successioni di configurazioni (cioè computazioni). Quindi dobbiamo aggiornare la definizione di quando la macchina accetta.

Definizione: la macchina non deterministica N decide I tutte e sole le volte che \(x \in I \iff \exists \text{ una computazione tale che } (q_0, \triangleright x, \triangleright, ..., \triangleright) \mapsto^\star_N (SI, w_1, w_2, ..., w_k)\) .

Da notare il fatto che questa definizione di accettazione introduca una asimmetria rispetto a quella di rifiuto: basta che esista una computazione accettante per accettare, quindi bisogna che tutte le computazioni siano di rifiuto per rifiutare (o siano non terminanti, ma a noi ora interessano solo problemi decidibili).

Complessità in tempo e spazio non deterministici

Introduciamo le classi di complessità non deterministiche corrispettive a quelle deterministiche che abbiamo già visto. Inizieranno con la lettera N per non determinismo.

Ricordiamo che consideriamo i soli problemi decidibili e che se una macchina N decide I, non solo si ha che \(\forall x \in I \exists w_1,w_2,...,w_k\) tali che \(N(x) = (q_0,\underline{\triangleright} x, \triangleright, ..., \triangleright) \mapsto^\star_N (SI, w_1,w_2,...,w_k)\) , ma anche che \(\forall x \notin I, \forall w_1,w_2,...,w_k . N(x) \mapsto^\star_N (NO,w_1,w_2,...,w_k)\) , cioè si raggiunge lo stato di rifiuto se x non appartiene a I.

Tempo non deterministico

Definizione: la macchina non deterministica \(N \text{, decide } I\) in tempo non deterministico \(f(n)\) se e soltanto se:

  • \(N \text{ decide } I\) e
  • \(\forall x \in I \> \exists t . (q_0,\underline{\triangleright}x, \triangleright,...,\triangleright) \mapsto^t_N (SI,w_1,w_2,...,w_k), t \leq f(|x|)\) , ovvero N accetta x in tempo non deterministico \(f(|x|)\) se e solo se c’è almeno una computazione che termina su uno stato di accettazione in t passi con t minore o uguale a \(f(|x|)\)

Ripetiamo che una macchina non deterministica N accetta x appartenente a I se esiste almeno una computazione che termina in meno di \(f(|x|)\) passi; mentre per rifiutare y che non appartiene a I (e quindi \(y \in \bar I\) ), tutte le computazioni che terminano in meno di \(f(|y|)\) passi devono essere di rifiuto.

Classe dei problemi decidibili in tempo non deterministico

Definizione: se una macchina di Turing non deterministica decide il problema I in tempo f, allora:

$$I \in \mathrm{NTIME}(f)$$

Classe dei problemi decidibili in tempo non deterministico polinomiale

Definizione: la classe dei problemi decidibili in tempo non deterministico polinomiale è:

$$\mathcal{NP} = \bigcup_{k \geq 1} \mathrm{NTIME}(n^k)$$

Il motivo per cui \(\mathcal{P} \subseteq \mathcal{NP}\) è che una MdT deterministica è anche non deterministica. Se fosse anche vero che \(\mathcal{P} \supseteq \mathcal{NP}\) allora si potrebbe concludere che \(\mathcal{P} = \mathcal{NP}\) , cioè esisterebbe un modo per trasformare algoritmi non deterministici polinomiali in uno deterministico polinomiale, quindi praticamente “facile e fattibile”.
Tuttavia il problema resta aperto e non è noto nessun algoritmo del genere, anzi si tende a credere che le due classi non coincidano e che alcuni problemi siano effettivamente più difficili di altri.

Complessità della simulazione non deterministica

Vediamo come una macchina deterministica simula una non deterministica. L’idea è quella di generare le possibili soluzioni e poi di verificare se sono tali.

Teorema: se I è deciso in tempo non deterministico \(f(n)\) dalla macchina non determistica N a k nastri, allora, con una perdita esponenziale, è deciso \(\mathcal{O}(c^{f(n)})\) da una macchina deterministica M a k + 1 nastri, con c > 1 dipendente solo da N. Più precisamente:

$$\mathrm{NTIME}(f(n)) \subseteq \mathrm{TIME}(c^{f(n)})$$

Dimostrazione: sia d il grado di non determinismo di N, cioè poniamo

$$d = \max\{Grado(q,\sigma) | q \in Q, \sigma \in \Sigma \}$$
con \(Grado(q, \sigma) = \#\{(q',\sigma',D) | ((q,\sigma), (q',\sigma',D)) \in \Delta\}\) , cioè Grado conta il numero di scelte disponibili quando la macchina si trova nello stato q e legge il simbolo σ dal nastro. La variabile d contiene il massimo grado, cioè il massimo numero di scelte che può fare N.

Per semplicità supponiamo che la macchina abbia sempre d scelte, quindi consideriamo un albero di scelte completo con fattore di diramazione d.

Per ogni stato \(q \in Q\) e ogni simbolo \(\sigma \in \Sigma\) , ordiniamo totalmente (e.g. lessico-graficamente) l’insieme \(\Delta(q,\sigma)\) .

Ogni computazione di N è una sequenza di scelte e se tale sequenza è lunga t, può essere vista come una sequenza di naturali nell’intervallo \([0, d-1]\) , cioè un numero in base d. La macchina M ha un nastro extra rispetto alla macchina N, sul quale viene codificata in un intero e memorizzata la successione di scelte presa in esame.

La macchina M si comporta così:

  1. inizializza il nastro extra con l’intero in base d che rappresenta la prima scelta da verificare (per semplicità diciamo che 0 codifica la prima successione di scelte).
  2. M legge il numero registrato sul nastro extra, lo decodifica e riproduce la successione di scelte rappresentate dal numero
  3. M simula quella porzione di computazione di N che verifica se la successione di scelte porta ad una soluzione accettabile.
  4. Se N termina in uno stato di accettazione, anche M termina e accetta, altrimenti genera la prossima successione di scelte codificandola e salvandola sul nastro extra
  5. Se N termina in uno stato di rifiuto e sono state generate tutte le possibili successioni di scelte allora anche M termina e rifiuta.
  6. M riparte dal punto 2, stavolta esaminando la successione di scelte successiva

Data questa costruzione M termina se e solo se N termina e M accetta se e solo se N accetta, quindi M e N calcolano la stessa funzione.

M deve visitare al caso pessimo un albero completo con fattore di diramazione d (ogni volta c’è da scegliere tra d diverse possibilità) e profondo \(f(n) + 1\) (ogni successione di scelte è lunga \(f(n)\) perché N calcola quel numero di passi per trovare il cammino accettante).
Di conseguenza abbiamo che M ha complessità \(\mathcal{O}(d^{f(n) + 1})\) e possiamo dimostrare il teorema ponendo c = d.

Spazio non deterministico

Definizione: la MdT N, non deterministica a k-nastri di tipo I/O, decide I in spazio non deterministico \(f(n)\) se e solamente se:

  • \(N \text{ decide } I\) e
  • \(\forall x \in I \> \exists w_1,w_2,...,w_k . (q_0, \underline{\triangleright}x,...,\underline{\triangleright}) \mapsto^\star_N (SI,w_1,w_2,...,w_k), \sum_{2 \leq i \leq k-1} |w_i| \leq f(|x|)\)

Classe dei problemi decidibili in spazio non deterministico

Definizione: se una macchina di Turing non deterministica decide il problema I in spazio \(f(n)\) , allora:

$$I \in \mathrm{NSPACE}(f(n))$$

Classe dei problemi decidibili in spazio non deterministico polinomiale

Definizione: la classe dei problemi decidibili in spazio non deterministico polinomiale è

$$\mathrm{NPSPACE} = \bigcup_{k \geq 1} \mathrm{NSPACE}(n^k)$$

Teorema di Savitch

L’estensione con il non determinismo non allarga la classe dei problemi trattabili in spazio polinomiale, ma lo fa solo con il tempo:

Teorema:

$$\mathrm{NPSPACE = PSPACE}$$

Non dimostro questo teorema, ma se ne può trovare lo scheletro su wikipedia.

Un esempio di problema che sta in NP, ma non in P è il problema del commesso viaggiatore.