Complessità della programmazione a vincoli

Qualcosa si è già visto:

• classi trattabili basate sulla consistenza locale (es. problemi binari aciclici)
• classi trattabili basate su metodi di decomposizione

Manca la sistematizzazione di queste cose

Cose da vedere

• complessità del caso generale
• tipi di restrizioni
• relazioni con altri problemi

Complessità del caso generale

Il problema è NP-completo

è in NP:

si tratta di trovare una valutazione per tutte le variabili tale che tutti i vincoli siano soddisfatti; verificare se tutti i vincoli sono soddisfatti è polinomiale;

è NP-hard:

si riesce ad esprimere 3SAT con facilità

NP-hardness

Codifichiamo 3SAT come problema di programmazione a vincoli

Tutte le variabili hanno dominio {0,1}

Per ogni clausola, si mette un vincolo che è soddisfatto se e solo se lo è la clausola

Per esempio, x ∨ ¬ y diventa questo vincolo:

Manca solo x=0,y=1, che è l'unica valutazione parziale che non soddisfa la clausola

Questa dimostrazione è abbastanza ovvia

Casi trattabili

Si tratta di dimostrare che per certi tipi di problemi la complessità scende a polinomiale

Alcuni casi li abbiamo già visti

Esempio: classe dei problemi binari aciclici

Caratteristica comune: per decidere se un problema sta in questa classe, i domini e le relazioni non servono

Sono classi definite solo in base agli scope dei vincoli

Restrizioni strutturali

Sono classi di problemi CSP definite in base soltanto agli scope dei vincoli

Quindi, per vedere se un problema sta in una classe, non servono domini e relazioni

Restrizione strutturale trattabile=una restrizione strutturale per la quale esiste un algoritmo polinomiale che risolve tutti i problemi della restrizione

Restrizioni relazionali

Sono restrizioni sui possibili domini e relazioni

Esempio (ovvio): restrizioni in cui tutte le relazioni contengono una sola tupla

Questa è una restruzione relazionale trattabile

Restrizioni relazionali

Sono classi di problemi definite solo guardando le relazioni e i domini

Quindi, si deve poter capire se un problema sta in una certa restrizione senza guardare gli scope dei vincoli

Esistono delle restrizioni relazionali trattabili

Restrizioni relazionali trattabili

Una restrizione relazionale trattabile è:

1. domini binari
2. relazioni a due colonne

È solo una riformulazione di 2SAT, che è polinomiale

Notare che la relazione sulla relazione in effetti impone ai vincoli di avere due variabili l'una

Non è una restrizione strutturale perchè gli altri vincoli in cui le variabili appaiono non hanno importanza

Dicotomie

In alcuni casi, è possibile dare delle condizioni su delle restrizioni, in modo tale che:

• se una restrizione soddisfa queste condizioni, allora è una restrizione trattabile
• altrimenti, risolvere i problemi della restrizione è NP-completo

Valgono per restrizioni di tipi particolari

Ora vediamo esempi

Teorema di Schaefer

Riguarda restrizioni relazionali su domini binari

In altre parole si considerano solo problemi i cui domini hanno solo due elementi

Si può assumere che i due elementi siano 0 e 1

Non si guardano gli scope dei vincoli, quindi sono restrizioni relazionali

Il teorema dice che una restrizione relazionale (un insieme di relazioni, dato che il dominio è fissato) di questo tipo è polinomiale se:

• i vincoli con queste relazioni sono sempre soddisfatti quando tutte le variabili valgono 0
• i vincoli con queste relazioni sono sempre soddisfatti quando tutte le variabili valgono 1
• le relazioni hanno tutte due colonne
• le relazioni rappresentano clausole Horn
• le relazioni rappresentano clausole dual-Horn
• le relazioni sono equivalenti ad equazioni affini (x₁ XOR ... XOR x_n = 1)

Cosa dice il teorema di Schaefer

Si considerano solo problemi di soddisfazione di vincoli in cui i domini hanno due elementi

Si consiera un insieme fissato di relazioni (che può anche essere infinito)

Se l'insieme di queste relazioni soddisfa una qualsiasi delle sei condizioni di prima:

esiste un algoritmo polinomiale che risolve i problemi che usano solo queste relazioni

Se invece l'insieme di queste relazioni non soddisfa:

l'insieme dei problemi che usano queste relazioni è NP-completo

Problema dell'omomorfismo

È un problema che proviene dalle basi di dati

Si tratta di verificare se certe relazioni si possono mappare in altre

Esiste una corrispondenza diretta con il problema della programmazione a vincoli

Strutture relazionali

Le strutture relazionale sono definite a partire da un vocabolario

Questo è un insieme di simboli di relazione, oguno con una arità

Si assume che il vocabolario sia fissato

Dato un vocabolario R₁,...,R_n, una struttura relazionale A è composta di:

• un insieme di valori VA
• una relazione RA₁ per ognuno dei simboli del vocabolario, con il numero opportuno di colonne

Si scrive di solito A=(VA,RA₁,...,RA_n)

Cos'è una struttura relazionale

Nelle basi di dati si può interpretare in questo modo:

• il vocabolario indica i nomi delle tabelle e i numero di colonne di oguna; questo si assume fissato
• il dominio indica i dati possibili
• le relazioni indicano il contenuto "corrente" della base di dati

Si assume (implicitamente) che tutti i dati abbiano lo stesso tipo

Altra interpretazione

Una query si può anche formulare come una struttura relazionale

In particolare, questo vale per le query congiuntive

Una query congiuntiva è un insieme di letterali del tipo R(var,...,var)

Questo letterale si può vedere come una tabella con una sola riga

È quindi una relazione di una struttura relazionale,

Dato che la relazione contiene variabili, il dominio è l'insieme delle variabili

Problema dell'omomorfismo

Si considera un vocabolario fissato

Ci sono due strutture sullo stesso vocabolario

Il problema è quello di vedere se è possibile "vedere" la prima struttura come un "sottoinsieme" della seconda

Omomorfismo: definizione

Sono date due strutture relazionali sullo stesso vocabolario

• A=(VA,RA₁,...,RA_n)
• B=(VB,RB₁,...,RB_n)

Un omomorfismo è una funzione h:VA → VB (una funzione che ha un valore di VA come argomento e un valore di VB come risultato), tale che:

• per ogni tupla (x₁,...,x_n) ∈ RA_i
• risulta che (h(x₁),...,h(x_n)) ∈ RB_i

Spiegazione

Si tratta di vedere se esiste una corrispondenza fra i domini in modo tale che la prima struttura diventa "una parte" della seconda

In particolare, con questa corrispondenza ogni relazione della prima struttura deve diventare un sottoinsieme della relazione corrispondente nella seconda struttura

Non è richiesto che la prima relazione diventi uguale alla seconda: basta che non abbia righe che nella seconda non ci sono

CSP-Omomorfismo

Un problema di CSP si può esprimere come il problema dell'omomorfismo:

• la prima struttura rappresenta variabili e scope di vincoli
• la seconda struttura rappresenta valori (dei domini) e relazioni

Il vocabolario è lo stesso ("nomi" di vincoli)

Nella prima struttura, il dominio sono le variabili; le relazioni sono gli scope dei vincoli

Il problema dell'omomorfismo diventa quello di dare valore alle variabili in modo tale che questi valori siano nella relazione di ogni vincolo

Quindi è il problema di soddisfare i vincoli

Trasformazione inversa

Dato un problema di omomorfismo, trovare un problema di soddisfazione di vincoli che sia equivalente

La difficoltà è soltanto che le relazioni della prima struttura possono contenere più tuple

Soluzione: si crea un vincolo per ognuna delle tuple di ogni relazione della prima struttura

Infatti, il problema è sempre quello di trovare valori per le variabili (valori della seconda struttura per i valori della prima) in modo tale che ogni riga della prima struttura (vincolo) diventi una riga nella seconda (sia soddisfatto, ossia la tupla sia nella relazione del vincolo)

Teorema di Hell-Nesetril

È una dicotomia

Si basa sempre sull'omomorfismo, però in questo caso si considerano solo grafi

Un grafo è una struttura relazionale in cui esiste un unico simbolo di relazione, che è binario

Questa relazione rappresenta la presenza degli archi

Una struttura relazionale è composta da un dominio (i nodi) e da una relazione (gli archi)

Il teorema dice che stabilire l'esistenza di un omomorfismo fra grafi è polinomiale se e solo se il secondo grafo è 2-colorabilie (ossia, è bipartito), e NP-completo altrimenti

In termini di CSP, questa condizione riguarda problemi in cui tutte i vincoli sono binari e hanno la stessa relazione, e questa relazione rappresenta un grafo 2-colorabile

Restrizioni non-uniformi

Una restrizione non-uniforme consiste nel considerare una singola seconda struttura relazionale nel problema dell'omomorfismo

Questo equivale a considerare un insieme fissato e finito di relazioni

È come una restrizione relazionale, ma il numero di relazioni ammesse è finito

Differenza: l'or fra un numero illimitato di variabili si realizza con una relazione per ogni numero di variabili

Quindi, non è ammesso in una restrizione non-uniforme

Restrizioni uniformi

Non è il contrario delle restrizioni uniformi

Si considera l'unione di un insieme di restrizioni non-uniformi

In altre parole, ogni restrizione non-uniforme è un insieme di problemi; l'unione di restrizioni non-uniformi è una restrizione uniforme

Una restrizione uniforme può anche essere composta da un insieme infinito di restrizioni non-uniformi

In questo caso, la restruzione uniforme può essere intrattabile anche se ognuna delle restruzioni non-uniformi è trattabile

Condizione sufficente basata su Datalog

Una query datalog booleana definisce una funzione da insiemi di letterali del tipo L(a₁,...,a_n) a {true,false}

Considerando gli insiemi per i quali il risultato è true, una query definisce un insieme di insiemi di letterali

Un insieme di letterali è in questo insieme se la query produce true come risultato

Anche una restrizione non-uniforme si può vedere in questo modo:

• l'insieme delle relazioni è fissato
• un problema è dato quindi da un insieme di coppie (scope,relazione)
• ogni coppia è quindi composta da una relazione e da una lista di variabili; è come un letterale, ma scritto in modo diverso

Quindi, anche una restrizione non-uniforme si può vedere come un insieme di letterali

Corrispondenza

Non tutti gli insiemi di letterali sono rappresentati da un programma Datalog

Vale però questa corrispondenza:

• una restrizione non-uniforme è trattabili
• se e solo se
• l'insieme dei letterali che rappresentano i problemi non soddisfacibili si può esprimere come un programma Datalog