06. Complessità computazionale del ragionamento con la default logic

Brave reasoning e conscious reasoning

Quanto costa, computazionalmente, applicare una di queste due semantiche? Ripetiamo le loro definizioni:

Semantica brave: Data una teoria di default DELTA è vero che una certa frase PHI deriva in senso brave da DELTA?
$\Delta \models_b \varphi \Leftrightarrow \exists \ E \ \mbox{estensione di} \ \Delta : E \models \varphi$
Ovvero basta un'estensione che derivi PHI per far derivare PHI da DELTA in senso brave.

Semantica cauta (conscious): Tutte le estensioni di DELTA devono derivare PHI per far si che PHI derivi da DELTA
$\Delta \models_c \varphi \Leftrightarrow \forall \ E \ \mbox{estensione di} \ \Delta : E \models \varphi$

L'esclusione principio del terzo escluso

Questo tipo di semantiche non incorporano (cioè non rispettano) il principio del terzo escluso (o principio di non contraddizione), ovvero con la semantica brave con una estensione potrei derivare a e con un'altra not a . Con la semantica cauta non deriverei nessuna delle due opzioni mentre il principio del terzo escluso prevede che si derivi almeno una delle opzioni.

Costo computazionale brave reasoning

Quanto costa derivare una formula PHI con il brave reasoning? Una possibilità è quella di calcolare la derivazione con un'unica formula logica che ammetta due quantificatori ( QBF con 2 quantificatori ), per prima l'esistenziale ( $\exists$ ) e poi l'universale ( $\forall$ ) applicati sulle variabili della formula stessa (la notazione è $QBF_{2\exists}$. Questo problema è molto costoso, rientra nella classe $\Sigma_P^2$ che è oltre NP.
Sostanzialmente data DELTA si parte dalla parte riguardante le certezze (W) e se ne trova il modello. Dato questo, analizzando i default, si cercano le estensioni. Solo che si vogliono le estensioni minimali1, quindi per ogni estensione bisogna vedere se è minimale. In sostanzia bisogna prima trovare tutte le estensioni di DELTA, e poi scegliere quelle minimali, ed è parecchio lavoro.

Costo computazionale semantica cauta

E' similare a quello della semantica brave, in sostanza si usa una formula come quella di prima ma dove le variabili sono quantificate prima universalmente e poi esistenzialmente ($QBF_{2\forall}$). Il costo computazionale è $\Sigma_P^2 \mbox{complete}$.

Oltre NP

$\Sigma_P^2$ è oltre Np come complessità, per capirci se per risolvere un problema in NP basta fare un backtracking (o, se si è su un albero, esplorare tutto l'albero), con $\Sigma_P^2$ servono due backtracking, uno per arrivare ad un certo stato e l'altro per esplorare di nuovo tutto in funzione di quello stato. Se fossimo su un albero, per ogni nodo dovremmo riesplorare tutto l'albero.

Disjunction free (DF) defaul logic

E' una variante della default logic che serve per diminuire la complessità dell'attuazione delle semantiche sopra esposte. In pratica le regole in W o i default (in qualsiasi punto, prerequisiti, giustificazioni o conseguenze) contengono solo congiunzioni ($a \wedge b$). Senza disgiunzioni calano sia la complessità che, ovviamente (c'è sempre un costo da pagare) l'espressività. La complessità scende da $\Sigma_P^2$ ad NP complete, poichè il costo di cercare un modello in W scende da NP a P2.

Default logic unaria

Altra restrizione, data la teoria di default DELTA, ogni default ha come prerequisito e conseguenza formule di taglia uno, cioè composte da un solo letterale, con l'eccezione che la conseguenza può avere taglia due se è composta dalla congiunzione di un letterale positivo ed uno negativo.
Con questa restrizione si perde di espressività (senza, tuttavia, toccare l'espressività di W) ma si scende ad una complessità pari ad NP complete con l'uso delle semantiche sopra esposte.

Default normali

Possiamo applicare la restrizione dei default normali sia alle teorie DF o alle teorie unarie, tuttavia non riusciamo a far scendere la complessità della semantica brave sotto NP complete.
Invece unendo tutte le restrizioni, ovvero DF + unario + normale, riesco ad ottenere che la semantica cauta ha un costo in P-time (e quindi anche la semantica brave visto che è meno costosa della cauta).

Nota: differenza tra problemi di ricerca di una soluzione rispetto a problemi di decisione.

Per quanto riguarda i problemi di decisione (ovvero stabilire se una soluzione esiste), le classi Co (tipo Co-NP) rispetto alle classi normali richiedono algoritmi con la stessa complessità delle classi normali. Invece per quanto riguarda la ricerca della soluzione (cioè una soluzione al problema), le classi Co richiedono algortimi più difficili.

Significato della complessità prima esposta, identificare i casi semplici.

La complessità di un problema ci indica che esiste almeno un'istanza di quel problema che richiede X risorse per esser risolta, ma non dice che ogni istanza di quel problema richiede X risorse per essere risolta, quindi possono benissimo esistere istanze semplici da risolvere di quel problema (basta pensare ad una teoria semplice).
Sarebbe interessante trovare un automatismo che riconosca i casi semplici da trattare da quelli difficili, ad esempio riconosca le teorie DF unarie normali tra tutte le teorie di default.
In sostanza vorremmo algoritmi che nei casi semplici (o ancor meglio in quelli tipici) siano efficienti, anche se in generale sono molto lenti.

Il problema è che riconoscere un'istanza del problema è un problema difficile di per sè, quindi siamo messi di fronte ad un tradeoff: se il riconoscimento del caso semplice costa quanto la soluzione di un caso difficile, tanto vale provare subito a risolvere il caso senza analizzare la sua difficoltà.

Nota: algoritmi potenzialmente complicati spesso sono i più semplici da usare

Non sempre, se un dato algoritmo è potenzialmente più semplice da usare di un altro, si usa questo algoritmo (vedi il ragionamento sopra esposto). Bisogna vedere la normalità dei casi. Ad esempio il mergesort ha una complessità $O (n \cdot log_2(n) )$ ma spesso si usa il quicksort che ha una complessità media uguale ma in generale ha la complessità $O(n^2)$ però, nel caso medio, consuma meno spazio.

Nota: differenza tra complessità ed espressività

La complessità di un formalismo (un algoritmo, un linguaggio, etc..) mi dice quante risorse richiede questo formalismo per risolvere un certo problema espresso tramite il formalismo stesso. L'espressività invece mi indica quali problemi il formalismo permette di trattare.
Un altro modo di classificare l'espressività di un problema è dire la massima classe di complessità a cui appartengono i problemi che riesce a trattare un formalismo. Se un formalismo è 'C' (classe di complessità generica) espressivo , allora la sua complessità deve essere C complete, altrimenti non è C espressivo. Quindi $espr(\mbox{formalismo}) \subset C$.

Esempio: Uso di modelli stabili o teorie "della certezza" positive

Vedere linguaggi formali, velocemente una teoria logica T (esposta sotto forma di regole, o almeno a noi interessano queste teorie) ha un modello stabile M se M è un modello minimale di $T^M$.
$T^M$ si costruisce così: date le regole di T, se in queste compaiono letterali negati i cui positivi sono in M, vengono tolte. Se invece il letterale negato è in M, il letterale viene sostituito con true.
Quindi $T^M$ è una teoria logica solo positiva.
Quindi, sostituendo questa teoria logica positiva a W, qual è la complessità di derivare PHI con il brave reasoning? (bisogna trovare almeno un'estensione tale che soddisfi $T^M$)
E' $\Sigma_P^2$ complete.

Dubbio: Ma se il brave reasoning è sigma p 2 completo con le teorie positive, perchè non lo è con teorie più generali (sopra è scritto: sigma pi 2 e basta). Chiedere.

Come espressività? Non è $\Sigma_P^2$ espressivo, ne NP espressivo e neanche P espressivo. Ad esempio il problema della parità di un predicato (se i fatti relativi ad un predicato sono in numero pari o dispari) non è risolvibile.

Questo è un esempio che esistono formalismi che richiedono molte risorse per il calcolo ma non sono così espressivi.

Richiamo classi di complessità

I problemi decidibili sono classificabili in classi di complessità computazionale, ovvero quante unità di tempo sono richieste (dato un certo mapping operazioni-tempo richiesto per eseguirle) per risolvere un dato problema. In particolare ci soffermiamo sui problemi di decisione (del tipo esiste o no una soluzione? E non: trova la soluzione e ritornamela).

Classi base

P è la classe dei problemi decisionali risolvibile in tempo polinomiale da MT (macchine di turing) deterministiche.
NP è la classe dei problemi decisionali risolvibili in tempo polinomiale da MT non deterministiche (che diventa tempo esponenziale per MT deterministiche). Oppure problemi per i quali esiste un certificato polinomiale (una soluzione di lunghezza polinomiale rispetto all'input del problema) che si può verificare in tempo polinomiale da MT deterministiche.
Per ora si ha la relazione (che potrebbe esser confutata) che $P \subset NP$.
Co-NP: è la classe duale ad NP, cioè sono i problemi duali. Se il problema è A, Co-NP cerca soluzioni a problemi A negato ("verifica che esiste x nell'insieme" -> CoNP:"verifica che x non appartenga all'insieme"). Le classi complementari (Co) sono distinte dalle classi normali solo oltre P (quindi per macchine non deterministiche), ciò vuol dire che P e Co-P fanno parte della stessa classe di complessità.

d14.jpg

Oracoli

Poi si prosegue con gli oracoli, ovvero si pensa ad una MT che può chiedere ad un'altra MT la soluzione di parti del problema. Questa seconda MT è detta oracolo e risponde istantaneamente (o meglio, la sua risposta costa una unità di tempo nel tempo della MT che ha fatto la richiesta) anche se in realtà eseguirebbe un certo numero di operazioni (in un certo tempo).
La classe $\Delta_2^P$ è la classe dei problemi risolvibili in tempo polinomiale su una MT deterministica avendo un oracolo che risolve problemi in NP.
$\Sigma_2^P$ problemi risolvibili da MT non deterministiche in tempo polinomiale avendo come oracolo una MT che risolve problemi in NP.
$\Sigma_k^P$ problemi risolvibili da MT non deterministiche in tempo polinomiale avendo come oracolo una MT che risolve problemi in $\Sigma_{k-1}^P$.
Le classi complementari a sigma sono: $\Pi_k^P$ cioè $\Pi_k^P = \mbox{Co-}\Sigma_k^P$.
Le classi $\Delta_k^P$ sono classi di problemi risolvibili da MT deterministiche che usano oracoli che risolvono problemi in $\Sigma_{k-1}^P$.
Poi ci sono le classi $D_k^P$ ovvero i problemi che appartengono alle intersezioni tra $\Pi_k^P$ e $\Sigma_k^P$.

Si ha la gerarchia seguente:

d15.jpg

La gerarchia cresce con $k \rightarrow +\infty$ e forma la gerarchia Ph. Questa è racchiusa nella gerarchia PSPACE (problemi risolvibili da MT deterministiche occupando uno spazio di lavoro polinomiale rispetto all'input). PSPACE è chiuso rispetto all'uso di MT deterministiche o non deterministiche (cioè lo spazio di lavoro richiesto non cambia) e rispetto ai problemi complementari (cioè i problemi ed i loro complementari sono racchiusi in PSPACE senza l'esistenza di Co-PSPACE).
Poi c'è la classe EXPTIME che contiene PSPACE, sono i problemi risolvibili da MT deterministiche in tempo esponenziale (già in NP il tempo è esponenziale per MT deterministiche, ma l'esponenzialità permane fino ad arrivare ad EXPTIME).

d16.jpg

Problemi più difficili di una classe di complessità, completezza

I problemi più difficili di una data classe di complessità sono quelli che sono difficili almeno quanto tutti gli altri problemi di quella classe (quindi potrebbero essere anche oltre quella classe) e sono problemi che stanno in quella classe e non oltre.
Per dimostrare che siano problemi difficili almeno quanto tutti gli altri bisogna per prima cosa trovare un problema difficile di riferimento, che è appurato sia difficile (tramite una dimostrazione più o meno lunga) quanto tutti gli altri problemi che potrebbero stare in quella classe di complessità, e poi ridurre questo problema al problema corrente3. Ad esempio per determinare i problemi più difficili della classe NP il problema di riferimento è il SAT.

Questa classe di problemi difficili rappresenta il bordo (o frontiera) della classe di complessità ed è individuata dalla notazione Classe-complete. Quindi esisteranno problemi P-complete , NP-complete, etc…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License