4      Comportamento di phase transition

Phase transition nel kSAT random

Il costo della ricerca kSAT random

Il modello a probabilità costante

Negli ultimi anni c'è stato un interessamento considerevole nella phase transition in tanti problemi NP­completi [11]. I problemi che sono molto sopravincolati sono irrisolvibili e di solito è facile determinare questo. Problemi che sono molto sottovincolati sono risolvibili e di solito è facile indovinare una delle tante soluzioni. Una phase transition tende a presentarsi in mezzo quando i problemi sono criticamente vincolati ed è difficile determinare se sono o no risolvibili. Tale comportamento è stato studiato intensivamente nel SAT negli ultimi cinque anni.

4.1     Phase transition nel kSAT random

Per il 2SAT random, si è dimostrato che la phase transition si presenta a L/N=1 [12], [53]. Per il 3SAT random, è stato dimostrato sperimentalmente che la phase transition si presenta intorno a  L/M=4.3 [15], [96]. I limiti teoretici hanno messo la phase transition per 3SAT random nell'intervallo 3.003 < L/N < 4.598 [28], [84]. Per il 4SAT random, è stato dimostrato sperimentalmente che la phase transition si presenta per L/N = 9.8 [40].

Per k grande, la phase transition per il kSAT random si presenta per il valore di L/N vicino a -1/log₂(1-1/2^k) [82 ]. Un recente risultato di Friedgut, dimostra che l'ampiezza della phase transition nel modello 3SAT random si restringe all'aumento della dimensione dei problemi [25 ]. Kamath e al. hanno dimostrato che alla transizione del 3SAT random, la distribuzione nel numero di assegnamenti soddisfacenti è molto distorsionato [73]. Un numero esponenzialmente piccolo di problemi ha un numero esponenzialmente grande di assegnamenti soddisfacenti. Questo rende difficile il calcolo della posizione della transizione.

Una tecnica prestata dalla meccanica statistica chiamata rappresentazione in scala di dimensione limitata [1] modella la forma della transizione della soddisfacibilità [82 ], [115 ]. Intorno al valore critico di L/N, la misurazione in scala di dimensione limitata predice che proprietà macroscopiche come la probabilità di soddisfacibilità sono quasi sempre indistinguibili.

La misurazione in scala dei costi della ricerca può essere accuratamente modellata utilizzando questa tecnica [33].

4.2     Il costo della ricerca kSAT random

Per i metodi completi come quello di Davis­Putnam, è stato osservato un massimo del costo medio della ricerca, nella phase transition del 3SAT random dove approssimativamente 50% di problemi sono soddisfacibili [96]. Crawford e Auton hanno riportato una semplice crescita esponenziale, per la loro procedura di Davis­Putnam, nella classe di problemi 3SAT random a l/n = 4.2 (nella phase transition) e a l/n = 10 (nella regione sopravincolata) [16]. Loro hanno registrato anche una crescita approssimativamente lineare per l/n = 1, 2 e 3 nella regione sottovincolata [16]. Gent e Walsh hanno riportato un comportamento simile nel modello a probabilità costante [39], [40].

L'analisi teoretica della procedura di Davis­Putnam è stata ristretta alla classe più facile di problemi a probabilità costante. Yugami ha sviluppato un modello teoretico approssimativo per il caso medio di complessità della procedura Davis­Putnam attraverso la phase transition del 3SAT random [127]. Mentre i risultati confermano gli esperimenti, la derivazione è complessa e produce solamente equazioni ricorsive.

Per i metodi di ricerca locale, Gent e Walsh hanno riportato una possibile crescita cubica nel costo di ricerca per GSAT nella phase transition per il 3SAT random [36]. Parkes e Walser anche hanno registrato una crescita sotto esponenziale per varie versioni della procedura GSAT nella phase transition del 3SAT random [105]. Gent e al. hanno esteso questi risultati al costo del modello di ricerca attraverso l’intera phase transition del 3SAT random [34]. Loro non sono stati capaci di mettere d'accordo i loro dati per il GSAT ad un modello di ricerca a crescita esponenziale, invece hanno utilizzato un semplice modello di legge potenza con due parametri che cresce non più veloce di n⁴.

Recentemente, ci sono stati analisi più dettagliate della distribuzione del costo di ricerca. Frost e Rish hanno proposto le distribuzioni modelling discrete run-time con funzioni di probabilità continue [29 ]. Loro hanno mostrato che sui problemi 3SAT random fortemente non soddisfacibili, la distribuzione run-time della procedura Davis-Putnam può essere modellata da una funzione con densità lognormale. Anche Hoos e Stutzle hanno modellato le distribuzioni run-time, concentrandosi sulle singole istanze di problemi per ridurre le discordanze [66], [67]. Loro hanno mostrato che le distribuzioni di run-time per algoritmi come il WalkSAT possono essere modellate spesso con una distribuzione esponenziale.

Queste confermano i risultati sperimentali [41] in cui si suggerisce che riavvii random offrono poco o nessun vantaggio con gli algoritmi che compiono random walk, così come gli algoritmi che tendono di non bloccarsi in un minimo locale.

4.3     Il modello a probabilità costante

Sono stati mostrati vari risultati teoretici per il modello a probabilità costante senza la cancellazione delle clausole unit o vuote. Per esempio, Purdom e Brown [108] mostrano che il tempo medio di funzionamento è polinomiale se qualsiasi del seguente è asintoticamente:

·      L £ MlnN per qualche M costante;

·      L ³ e^eN per qualche e costante;

·      p ³ e;

·      p £ Mln(N/N)^3/2.

Comunque, è importante notare che questi risultati non coprono tutte le funzioni possibili di p e L, e non nella copertura limite della phase transition tra soddisfacibile e non soddisfacibile.

La maggior parte degli studi sperimentali ha utilizzato il modello CP, in cui le clausole unit e vuote sono cancellate per prevenire i problemi banalmente irrisolvibili. Se la lunghezza attesa della clausola è tenuta costante variando poi  p come 1/n, allora la solubilità della phase transition è approssimativamente uguale al valore costante L/N [40]. Mentre i problemi dal modello CP sono tipicamente molto più facili dei problemi kSAT random della stessa dimensione [96], i problemi occasionali nella regione risolvibile easy possono essere molto più difficili per la procedura Davis­Putnam dei problemi più difficili della regione hard del modello kSAT random [39], [40]. Tali problemi avvengono in una regione dove constraint propagation è meno efficace, la profondità della ricerca è massima e l’euristica di ramificazione può commettere errori occasionali molto costosi [42].