An Efficient Algorithm for Solving the 2-MAXSAT Problem

Sintesi Tecnica: Un Algoritmo Efficiente per Risolvere il Problema 2-MAXSAT

Definizione del Problema
Il documento affronta il problema 2-MAXSAT, una versione ristretta del problema di Massima Soddisfacibilità (MAXSAT). Data un insieme $V$ di $m$ variabili booleane e una collezione $C$ di $n$ clausole in Forma Normale Congiuntiva (CNF), dove ogni clausola contiene al massimo due letterali, l'obiettivo è trovare un assegnamento di verità che massimizzi il numero di clausole soddisfatte. Il problema è stabilito come NP-completo, anche sotto questa restrizione.

Metodologia
L'algoritmo proposto si discosta dai tradizionali metodi branch-and-bound o di approssimazione trasformando il problema in un compito di massimizzazione della Forma Normale Disgiuntiva (DNF) e utilizzando una struttura di ricerca specializzata basata su grafi. La metodologia procede in tre fasi principali:

1. Trasformazione in DNF:
   L'algoritmo costruisce una nuova formula $D$ in DNF dalla formula CNF originale $C$. Per ogni clausola $C_i = l_{i1} \lor l_{i2}$ in $C$, l'algoritmo introduce una nuova variabile ausiliaria $x_i$ e genera due congiunzioni: $D_{i1} = l_{i1} \land x_i$ e $D_{i2} = l_{i2} \land \neg x_i$. La formula $D$ risultante consiste in $2n$ congiunzioni. La Proposizione 1 nel documento stabilisce che $C$ ha almeno $n^*$ clausole soddisfacibili se e solo se $D$ ha almeno $n^*$ congiunzioni soddisfacibili sotto un assegnamento di verità per $V \cup \{x_1, \dots, x_n\}$.

2. Rappresentazione Grafica (p-grafi e Trie):*
   Per rappresentare efficientemente gli assegnamenti di verità che soddisfano le congiunzioni in $D$, il documento introduce il p-grafo*.

   • Sequenze di Variabili: Ogni congiunzione viene convertita in una sequenza di variabili ordinata in base alla frequenza globale di apparizione delle variabili. I letterali negativi sono gestiti introducendo una notazione speciale $(c, *)$, che rappresenta il fatto che la variabile $c$ può essere vera o falsa (o saltata) senza influenzare la verità della congiunzione.
   • p-grafi: Un grafo diretto che rappresenta una singola congiunzione dove i nodi corrispondono alle variabili nella sequenza. Gli "span" (archi che saltano le variabili) rappresentano le opzioni $(c, *)$.
   • p-grafi:* Un raffinamento dei p-grafi in cui gli "span sovrapposti" (variabili opzionali consecutive) vengono uniti tramite chiusura transitiva. Ciò assicura che il grafo rappresenti correttamente tutti gli assegnamenti di verità validi per una specifica congiunzione.
   • Struttura tipo Trie ($G$): Tutti i p*-grafi sono integrati in un unico grafo di tipo trie $G$. Questa struttura raggruppa le sequenze di variabili comuni per evitare controlli ridondanti. Il grafo include "nodi di diramazione" dove i percorsi divergono.

3. Ricerca Ricorsiva Bottom-Up:
   Il core dell'algoritmo, SEARCH(G), esplora il grafo $G$ in modo bottom-up (post-order) per trovare il massimo sottoinsieme di congiunzioni soddisfacibili.

   • Sottoinsiemi Raggiungibili (RS): Per un nodo di diramazione $v$, l'algoritmo calcola i "sottoinsiemi raggiungibili" dei nodi raggiungibili tramite span dagli antenati. Questi sottoinsiemi rappresentano gruppi di congiunzioni che possono essere soddisfatte simultaneamente bypassando determinate variabili.
   • Confini Superiori (upBounds): Basandosi sugli RS, l'algoritmo identifica i "confini superiori" — insiemi di nodi che permettono la fusione di sottografi.
   • Costruzione Ricorsiva: Quando viene incontrato un nodo di diramazione, l'algoritmo costruisce un nuovo sottografo più piccolo, di tipo trie, radicato nei nodi del confine superiore. Un radice virtuale (il nodo di diramazione originale) viene aggiunta per mantenere la connettività. L'algoritmo chiama ricorsivamente SEARCH su questi sottografi.
   • Ottimizzazione: Per prevenire calcoli ridondanti, l'algoritmo impiega due miglioramenti: (1) limitare i calcoli RS al segmento tra il nodo di diramazione corrente e il suo antenato di diramazione più basso, e (2) utilizzare un array hash per memorizzare i risultati di sottografi precedentemente visitati, sopprimendo chiamate ricorsive ripetute.

Contributi Chiave

• Tecnica di Trasformazione: Una riduzione in tempo polinomiale del problema 2-MAXSAT al problema della massima congiunzione soddisfacibile in DNF.
• Struttura p-grafo:* La definizione di p*-grafi e della loro chiusura transitiva per rappresentare in modo accurato e compatto gli assegnamenti di verità per congiunzioni contenenti variabili opzionali.
• Ricerca Ricorsiva su Trie: Un nuovo algoritmo ricorsivo che costruisce e cerca dinamicamente una struttura di grafo tipo trie, utilizzando "sottoinsiemi raggiungibili" e "confini superiori" per fondere efficientemente gli spazi di soluzione.
• Analisi della Complessità: Il documento fornisce un'analisi dettagliata sostenendo che l'algoritmo opera entro limiti di tempo polinomiali.

Risultati e Complessità
Il documento afferma che la complessità temporale nel caso peggiore del proposto algoritmo è limitata da $O(n^2 m^4)$, dove $n$ è il numero di clausole e $m$ è il numero di variabili.

• La costruzione del trie iniziale e dei p*-grafi richiede $O(nm^2)$.
• La ricerca ricorsiva coinvolge al massimo $O(nm)$ nodi di diramazione.
• Ogni nodo di diramazione è coinvolto in al massimo $O(m)$ chiamate ricorsive a causa della riduzione dell'altezza del grafo ad ogni passaggio.
• Il costo per costruire un sottografo per chiamata è $O(nm^2)$.
• Combinando questi fattori, si ottiene il limite $O(n^2 m^4)$.

Significato e Rivendicazioni
Il documento conclude che, poiché il problema 2-MAXSAT è noto per essere NP-completo, l'esistenza di un algoritmo in tempo polinomiale per risolverlo costituisce una prova che P = NP. Gli autori dichiarano che questo risultato fornisce una prova di P = NP, alterando fondamentalmente la comprensione della complessità computazionale per i problemi di soddisfacibilità. Il lavoro è presentato come una modifica ed estensione di un articolo di conferenza, supportato da NSERC, Canada.