problemi di implementazione in 2-Soddisfacibilità problema

Question

Voglio realizzare 2-SAT problema per 100000 letterali. Quindi ci sarebbe 200000 vertici. Così mi sono bloccato di avere una vasta gamma di tutti i vertici raggiungibili da ogni vertice, spazio complessità O(200000^2), che è praticamente impossibile Quindi, per favore suggerire una soluzione per questo. E vi prego di far luce su un'efficace attuazione della 2-SAT problema.

Answer 1

wikipedia :

  

... 2-soddisfacibilità può essere risolto in tempo polinomiale. Come Aspvall, Plass & Tarjan (1979) osservati, un'istanza 2-satisfiability è risolvibile se e solo se ogni variabile dell'istanza appartiene a un diverso componente fortemente connessa del grafo delle implicazioni che la negazione della stessa variabile. Poiché componenti fortemente connesse possono essere trovati in tempo lineare da un algoritmo basato sulla ricerca in profondità, allo stesso tempo lineare vincolato vale anche per 2-satisfiability.

Io non pretendo di capire la maggior parte di tale paragrafo, ma sembrerebbe che ci è un algoritmo che può essere utilizzato per risolvere il problema 2-SAT, ed è descritto all'interno di tale riferimento documento ( Un algoritmo lineare tempo per testare la verità di certe formule booleane quantificati ). Si può apparentemente essere acquistato online per circa $ 20 USD. Non sono sicuro se questo è utile o meno, ma è così!

Aggiornamento: A PDF gratuito dello stesso documento può essere trovato qui . Merito va a Liori per la scoperta.

Answer 2

Tutta questa discussione è un po 'incasinato. Sì, si può risolvere 2-sat in un tempo lineare, ma no - non si può risolvere per che molte variabili. Il tempo per risolvere 2-Sat è lineare rispetto al numero delle implicazioni, che per 200 000 variabili potrebbe arrivare fino a (200000 * 199999) / 2 e, inoltre, se si utilizza questa soluzione è necessario circa la stessa quantità di memoria . C'è un'altra soluzione (non si utilizza componenti fortemente connesse che è più lento, ma non ha bisogno più di tanto la memoria).