|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-ComplessitàCircuitale History
Hide minor edits - Show changes to output
Changed lines 11-12 from:
''f: {0,1}'^2^' -> {0,1}'^m^' '' to:
''f: {0,1}'^n^' -> {0,1}'^m^' '' Changed lines 83-85 from:
* '''fan-in''', numero di archi entranti in un dato nodo. Il ''fan-in di un circuito'' è il numero massimo di fan-in calcolato sull'insieme di tutti i nodi;
* '''fan-out''', numero di archi uscenti da un dato nodo. Il ''fan-out di un circuito'' è il numero massimo di fan-out calcolato sull'insieme di tutti i nodi. to:
* '''fan-in''', numero di archi entranti in un nodo. Il ''fan-in di un circuito'' è il numero massimo di fan-in calcolato sull'insieme dei nodi;
* '''fan-out''', numero di archi uscenti da un nodo. Il ''fan-out di un circuito'' è il numero massimo di fan-out calcolato sull'insieme dei nodi. Changed lines 92-94 from:
Una '''famiglia di circuiti''' C è una lista infinita di circuiti, (C'_0_', C'_1_', C'_2_', ...), dove C'_n_' ha ''n'' variabili di ingresso. Diciamo che C decide un linguaggio A su {0,1} se, per ogni stringa w, \\
w appartiene ad A se e solo se C'_n_'(w)=1,\\
dove ''n'' in questo caso è la lunghezza di w. to:
Una '''famiglia di circuiti''' C è una lista infinita di circuiti, (C'_0_', C'_1_', C'_2_', ...), dove C'_n_' ha ''n'' variabili di ingresso. Diciamo che C decide un linguaggio A su {0,1} se, per ogni stringa w, w appartiene ad A se e solo se C'_n_'(w)=1, dove ''n'' in questo caso è la lunghezza di w. Changed line 97 from:
Per arrivare a definire la size-complexity di un circuito dobbiamo prima introdurre un po' di concetti: to:
Per arrivare a definire la ''size-complexity'' di un circuito dobbiamo prima introdurre un po' di concetti: Changed lines 99-100 from:
* due circuiti si dicono equivalenti quando con le stesse variabili in ingresso producono lo stesso valore in uscita per qualsiasi assegnamento passato in ingresso;
* un circuito è di ''dimensione minima'' se non esiste un circuito equivalente con dimensione inferiore. A dirlo è semplice, ma a verificarlo è un guaio; to:
* due circuiti si dicono equivalenti quando con le stesse variabili in ingresso producono lo stesso valore in uscita per qualsiasi assegnamento sugli ingressi;
* un circuito è di ''dimensione minima'' se non esiste un circuito equivalente con dimensione inferiore. A dirlo è semplice, a verificarlo è un guaio; Changed line 111 from:
Stesso discorso: arriveremo alla definizione della depth-complexity di un circuito solo dopo aver introdotto alcuni concetti basilari: to:
Stesso discorso: arriveremo alla definizione della ''depth-complexity'' di un circuito solo dopo aver introdotto alcuni concetti basilari: Changed lines 124-125 from:
Esiste una relazione tra le complessità circuitali di un linguaggio e la tempo-complessità del linguaggio stesso. Intuitivamente siamo infatti portati a pensare che ogni linguaggio con ridotta complessità nel tempo abbia anche una piccola complessità circuitale. Per chi però non si fidasse del proprio intuito, eccoci servito il Teorema 1: to:
Esiste una relazione tra la complessità circuitale e la tempo-complessità di un linguaggio. Intuitivamente siamo infatti portati a pensare che ogni linguaggio con ridotta complessità nel tempo abbia anche una piccola complessità circuitale. Per chi però non si fidasse del proprio intuito, eccoci servito il Teorema 1: Changed line 127 from:
Sia t:N->N una funzione con t(n)>=n. Se A appartiente a TIME(t(n)), allora A ha una complessità circuitale pari a O(t^2^(n)). to:
Sia t:N->N una funzione con t(n)>=n. Se A appartiente a TIME(t(n)), allora A ha una complessità circuitale pari a O(t'^2^'(n)). Changed lines 158-160 from:
La [@prima condizione@] è verificata grazie alla dimostrazione del Teorema 1, in cui si mostrava possibile utilizzare una MdT [@n.d.@] per simulare un circuito.
Per [@la seconda condizione@] proveremo a ridurre il problema CIRCUIT-SAT in quello 3SAT in tempo polinomiale. Si parla perciò di una riduzione da un circuito C a una formula Φ, tale che C è soddisfacibile se e solo se Φ lo è.\\ to:
La [@prima condizione@] è verificata grazie alla dimostrazione del Teorema 1, in cui si mostrava possibile l'utilizzo di una MdT [@n.d.@] per simulare un circuito.
Per [@la seconda condizione@] proveremo a ridurre il problema CIRCUIT-SAT a quello 3SAT in tempo polinomiale. Si parla perciò di una riduzione da un circuito C a una formula Φ, tale che C è soddisfacibile se e solo se Φ lo è.\\
Changed line 169 from:
to:
->Attach:IT-not1-3SAT.gif Changed lines 171-172 from:
to:
->Attach:IT-not2-3SAT.gif Changed line 175 from:
to:
->Attach:IT-and1-3SAT.gif Changed lines 177-178 from:
to:
->Attach:IT-and2-3SAT.gif Changed line 181 from:
to:
Changed line 183 from:
to:
Changed lines 17-18 from:
(:cellnr align=center bgcolor=#f2f6f9:)x
(:cell align=center bgcolor=#f2f6f9:)f'_1_' to:
(:cellnr align=center bgcolor=#d4e1f0:)x
(:cell align=center bgcolor=#d4e1f0:)f'_1_' Changed lines 43-44 from:
(:cellnr align=center bgcolor=#f2f6f9:)x'_1_'
(:cell align=center bgcolor=#f2f6f9:)x'_2_' to:
(:cellnr align=center bgcolor=#d4e1f0:)x'_1_'
(:cell align=center bgcolor=#d4e1f0:)x'_2_'
Changed lines 17-21 from:
(:cellnr align=center bgcolor=f2f6f9:)x
(:cell align=center bgcolor=f2f6f9:)f'_1_'
(:cell align=center bgcolor=f2f6f9:)f'_2_'
(:cell align=center bgcolor=f2f6f9:)f'_3_'
(:cell align=center bgcolor=f2f6f9:)f'_4_' to:
(:cellnr align=center bgcolor=#f2f6f9:)x
(:cell align=center bgcolor=#f2f6f9:)f'_1_'
(:cell align=center bgcolor=#f2f6f9:)f'_2_'
(:cell align=center bgcolor=#f2f6f9:)f'_3_'
(:cell align=center bgcolor=#f2f6f9:)f'_4_' Changed lines 43-47 from:
(:cellnr align=center bgcolor=f2f6f9:)x'_1_'
(:cell align=center bgcolor=f2f6f9:)x'_2_'
(:cell align=center bgcolor=f2f6f9:)f'_1_'
(:cell align=center bgcolor=f2f6f9:)...
(:cell align=center bgcolor=f2f6f9:)f'_16_' to:
(:cellnr align=center bgcolor=#f2f6f9:)x'_1_'
(:cell align=center bgcolor=#f2f6f9:)x'_2_'
(:cell align=center bgcolor=#f2f6f9:)f'_1_'
(:cell align=center bgcolor=#f2f6f9:)...
(:cell align=center bgcolor=#f2f6f9:)f'_16_' Changed line 169 from:
%center%Attach:IT-not1-3SAT.gif
to:
Changed lines 171-172 from:
%center%Attach:IT-not2-3SAT.gif
to:
Changed line 175 from:
%center%Attach:IT-and1-3SAT.gif
to:
Changed lines 177-178 from:
%center%Attach:IT-and2-3SAT.gif
to:
Changed line 181 from:
%center%Attach:IT-or1-3SAT.gif
to:
Changed line 183 from:
%center%Attach:IT-or2-3SAT.gif
to:
Added lines 1-193:
(:title Informatica Teorica - Complessità circuitale :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Complessità circuitale ::'''
%center% %sottotitolo% Appunti & Dimostrazioni del 26 Maggio
!!Funzioni booleane
Una ''funzione booleana'' ''f'' con ''n'' ingressi ed ''m'' uscite è una funzione che associa ad ogni stringa binaria di lunghezza ''n'' una stringa binaria di lunghezza ''m'', ovvero:\\
''f: {0,1}'^2^' -> {0,1}'^m^' ''
Data una funzione f che appartiene alla classe B'_n_' (con ''n'' numero di variabili), il numero di stringhe che può avere in ingresso è 2'^n^', mentre le diverse funzioni booleane ottenibili sono 2 elevato alla 2'^n^'. \\
Consideriamo ad esempio una B'_1_':
(:table width=40% align=center:)
(:cellnr align=center bgcolor=f2f6f9:)x
(:cell align=center bgcolor=f2f6f9:)f'_1_'
(:cell align=center bgcolor=f2f6f9:)f'_2_'
(:cell align=center bgcolor=f2f6f9:)f'_3_'
(:cell align=center bgcolor=f2f6f9:)f'_4_'
(:cellnr align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)1
(:cell align=center:)1
(:cellnr align=center:)1
(:cell align=center:)0
(:cell align=center:)1
(:cell align=center:)0
(:cell align=center:)1
(:tableend:)
Come ci aspettavamo, con una variabile abbiamo 2'^1^'=2 stringhe in ingresso, e 2'^2^'=4 funzioni in uscita. In particolare, per quanto riguarda queste ultime:
* f'_1_' è la funzione costante uguale a 0;
* f'_2_' è la funzione identità;
* f'_3_' è la funzione complemento;
* f'_4_' è la funzione costante uguale a 1.
Consideriamo come secondo esempio una B'_2_', per la quale ci aspetteremo di avere 2'^2^'=4 possibili stringhe in ingresso, e 2'^4^'=16 funzioni in uscita.
(:table width=40% align=center:)
(:cellnr align=center bgcolor=f2f6f9:)x'_1_'
(:cell align=center bgcolor=f2f6f9:)x'_2_'
(:cell align=center bgcolor=f2f6f9:)f'_1_'
(:cell align=center bgcolor=f2f6f9:)...
(:cell align=center bgcolor=f2f6f9:)f'_16_'
(:cellnr align=center:)0
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)...
(:cell align=center:)1
(:cellnr align=center:)0
(:cell align=center:)1
(:cell align=center:)0
(:cell align=center:)...
(:cell align=center:)1
(:cellnr align=center:)1
(:cell align=center:)0
(:cell align=center:)0
(:cell align=center:)...
(:cell align=center:)1
(:cellnr align=center:)1
(:cell align=center:)1
(:cell align=center:)0
(:cell align=center:)...
(:cell align=center:)1
(:tableend:)
Per rapidità non sono stati riportati in tabella tutti i valori delle funzioni intermedie, ma è importante sottolineare che ognuna di esse è ottenibile dalla combinazione dei connettivi logici applicati alle due variabili. L'insieme dei connettivi che permettono di esprimere tutte le funzioni booleane di una classe B'_n_' sono chiamati ''base'' per B'_n_', la più utilizzata delle quali è la '''base canonica''', composta dagli operatori AND, OR e NOT.
!!Circuiti booleani
I '''circuiti booleani''' sono un modello di calcolo diverso rispetto a quello delle MdT, e rappresentano la controparte teorica dei circuiti digitali.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Un '''circuito booleano''' è un grafo diretto e aciclico, i cui nodi sono etichettati. Distinguiamo:
* ''nodi di ingresso'', privi di archi entranti e etichettati con una variabile booleana o una costante (0/1);
* ''nodi operazione'' (o ''porte''), dotati di archi entranti e uscenti, ed etichettati con il simbolo di una funzione booleana di uno o più argomenti (il loro numero dipende da quello degli archi che entrano nel nodo);
* ''nodi di uscita'', privi di archi uscenti e con esattamente un arco entrante, sono etichettati con un diverso simbolo di variabile.
>><<
Altri due concetti importanti sono quelli di:
* '''fan-in''', numero di archi entranti in un dato nodo. Il ''fan-in di un circuito'' è il numero massimo di fan-in calcolato sull'insieme di tutti i nodi;
* '''fan-out''', numero di archi uscenti da un dato nodo. Il ''fan-out di un circuito'' è il numero massimo di fan-out calcolato sull'insieme di tutti i nodi.
Un circuito booleano C con ''n'' nodi di ingresso ed ''m'' nodi di uscita calcola la funzione f:{0,1}'^n^'->{0,1}'^m^' se, per ogni assegnamento di valori alle ''n'' variabili che etichettano i nodi di ingresso, il valore calcolato da C è uguale a f(x'_1_',x'_2_',...,x'_n_').
!!Circuiti e linguaggi
Una volta codificati opportunamente i linguaggi in binario, il nostro obiettivo è quello di usare i circuiti booleani per verificarli. Ma i circuiti hanno un numero fisso di ingressi, mentre i linguaggi possono contenere stringhe di lunghezze diverse, quindi che si fa? Semplice: invece di usare un unico circuito per verificare l'appartenenza a un linguaggio ne useremo un'intera ''famiglia''!
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Una '''famiglia di circuiti''' C è una lista infinita di circuiti, (C'_0_', C'_1_', C'_2_', ...), dove C'_n_' ha ''n'' variabili di ingresso. Diciamo che C decide un linguaggio A su {0,1} se, per ogni stringa w, \\
w appartiene ad A se e solo se C'_n_'(w)=1,\\
dove ''n'' in questo caso è la lunghezza di w.
>><<
!!Complessità di un circuito
!!!Legata alla dimensione
Per arrivare a definire la size-complexity di un circuito dobbiamo prima introdurre un po' di concetti:
* la ''dimensione'' ('''size''') di un circuito è pari al numero di porte che esso contiene;
* due circuiti si dicono equivalenti quando con le stesse variabili in ingresso producono lo stesso valore in uscita per qualsiasi assegnamento passato in ingresso;
* un circuito è di ''dimensione minima'' se non esiste un circuito equivalente con dimensione inferiore. A dirlo è semplice, ma a verificarlo è un guaio;
* una famiglia di circuiti è minimale se ogni circuito della sua lista ha dimensione minima;
* la ''size-complexity'' di una famiglia di circuiti (C'_0_', C'_1_', C'_2_', ...) è la funzione f:N->N dove f(n) è la dimensione di C'_n_'.
Abbiamo tutto quello che ci serve per affermare che:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
La '''size-complexity''' circuitale di un linguaggio è la size-complexity della famiglia minimale di circuiti per quel linguaggio.
>><<
!!!Legata alla profondità
Stesso discorso: arriveremo alla definizione della depth-complexity di un circuito solo dopo aver introdotto alcuni concetti basilari:
* la ''profondità'' ('''depth''') di un circuito è pari alla lunghezza (il numero di fili) del percorso più lungo tra ingresso e uscita;
* un circuito è di ''profondità minima'' se non esiste un circuito equivalente con profondità inferiore;
* una famiglia di circuiti è minimale se ogni circuito della sua lista ha profondità minima;
* la ''depth-complexity'' di una famiglia di circuiti (C'_0_', C'_1_', C'_2_', ...) è la funzione f:N->N dove f(n) è la profondità di C'_n_'.
Abbiamo tutto quello che ci serve per affermare che:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
La '''depth-complexity''' circuitale di un linguaggio è la depth-complexity della famiglia minimale di circuiti per quel linguaggio.
>><<
!!!Teorema 1 - Relazioni tra complessità
Esiste una relazione tra le complessità circuitali di un linguaggio e la tempo-complessità del linguaggio stesso. Intuitivamente siamo infatti portati a pensare che ogni linguaggio con ridotta complessità nel tempo abbia anche una piccola complessità circuitale. Per chi però non si fidasse del proprio intuito, eccoci servito il Teorema 1:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Sia t:N->N una funzione con t(n)>=n. Se A appartiente a TIME(t(n)), allora A ha una complessità circuitale pari a O(t^2^(n)).
>><<
La dimostrazione non è richiesta, ma è importante ricordare che oltre al teorema in sé prova anche che un circuito booleano può essere simulato da una MdT.
!!Teorema 2 - CIRCUIT-SAT è NP-completo
Così come per le formule booleane, anche i circuiti booleani possono essere o meno soddisfacibili; in particolare, lo sono quando una certa configurazione di valori passati agli ingressi fa sì che l'uscita del circuito sia pari a 1.\\
Il problema CIRCUIT-SAT si occupa di verificare se un circuito è soddisfacibile, o più formalmente:\\
[@CIRCUIT-SAT = {<C> | C è un circuito booleano soddisfacibile}@]
Vediamo ora il teorema:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
CIRCUIT-SAT è NP-completo.
>><<
!!Teorema 3 - 3SAT strikes back!
Ricordiamo che i 3CNF-formula sono formule in forma normale congiuntiva con clausole composte da 3 letterali, e che una 3SAT è una 3CNF-formula soddisfacibile. Il teorema:
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
3SAT è NP-completo.
>><<
'''Dimostrazione'''
Che 3SAT fosse NP-completo l'avevamo già dimostrato col teorema di Cook-Levin nel capitolo sulla [[NP-Completezza->IT-NP-Completezza]], ma volete mettere ridimostrarlo con i circuiti booleani?
Come sappiamo, un linguaggio B è NP-completo se soddisfa due condizioni:
* B è in NP;
* ogni A in NP è tempo polinomiale riducibile a B.
La [@prima condizione@] è verificata grazie alla dimostrazione del Teorema 1, in cui si mostrava possibile utilizzare una MdT [@n.d.@] per simulare un circuito.
Per [@la seconda condizione@] proveremo a ridurre il problema CIRCUIT-SAT in quello 3SAT in tempo polinomiale. Si parla perciò di una riduzione da un circuito C a una formula Φ, tale che C è soddisfacibile se e solo se Φ lo è.\\
Le variabili di un circuito sono gli ingressi x'_1_',...,x'_l_' e le porte g'_1_',...,g'_m_', che dovranno essere rimappate nelle variabili di Φ etichettate come w'_1_',...,w'_l+m_'.\\
Passiamo ora a costruire le clausole, che dovranno descrivere i tre operatori logici della forma canonica (AND, OR, NOT). Per semplicità utilizzeremo anche l'operatore implica, per il quale vale la proprietà:\\
[@(P->Q) = (~P v Q)@]
* Operatore '''NOT'''.
->Sia w'_i_' l'ingresso e w'_j_' l'uscita:
%center%Attach:IT-not1-3SAT.gif
->che diventa:
%center%Attach:IT-not2-3SAT.gif
* Operatore '''AND'''.
->Siano w'_i_' e w'_j_' gli ingressi e w'_k_' l'uscita:
%center%Attach:IT-and1-3SAT.gif
->che diventa:
%center%Attach:IT-and2-3SAT.gif
* Operatore '''OR'''.
->Siano w'_i_' e w'_j_' gli ingressi e w'_k_' l'uscita:
%center%Attach:IT-or1-3SAT.gif
->che diventa:
%center%Attach:IT-or2-3SAT.gif
A queste clausole ne aggiungiamo un'altra: (w'_m_'), che rappresenta il nodo di uscita del circuito C.
Quello che resta da fare è riscrivere le clausole in forma 3SAT (tre letterali per clausola). Dato che le uniche clausole a non essere in 3SAT (quelle del NOT e quella di uscita) hanno meno di 3 letterali, basterà semplicemente replicare un letterale quante volte serve per arrivare a 3, e metterlo in OR con gli altri. Ad esempio (w'_m_') diventa:\\
(w'_m_' v w'_m_' v w'_m_')
Ora che sappiamo come convertire variabili e porte logiche di un circuito in una formula 3SAT equivalente, possiamo affermare che se CIRCUIT-SAT è NP-completo (Teorema 2) allora anche 3SAT lo è, perché la riduzione da uno all'altro è tempo polinomiale nella dimensione del circuito iniziale.
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
