les questions de mise en œuvre dans le problème 2-Satisfiabilité

Question

Je veux mettre en œuvre problème 2-SAT pour 100000 littéraux. Donc, il y aurait 200000 sommets. Donc, je suis coincé d'avoir un tableau de tous les sommets accessibles depuis chaque sommet, la complexité de l'espace de O(200000^2) qui est infaisable Alors s'il vous plaît proposer une solution pour cela. Et s'il vous plaît jeter un peu de lumière sur la mise en œuvre efficace du problème 2-SAT.

Answer 1

De wikipedia :

  

... 2-satisfiabilité peut être résolu en temps polynomial. Comme Aspvall, Plass & Tarjan (1979) observée, une instance 2-satisfiabilité est résoluble si et seulement si toutes les variables de l'instance appartient à un autre composant fortement connexe du graphe d'implication que la négation de la même variable. Étant donné que se trouvent des composants fortement connectés en temps linéaire par un algorithme basé sur la profondeur première recherche, en même temps linéaire lié applique aussi bien à 2 satisfiability.

Je ne vais pas faire semblant de comprendre la plupart de ce paragraphe, mais il semblerait qu'il y ait un algorithme qui peut être utilisé pour résoudre le problème 2-SAT, et il est décrit dans ce référencé Document ( Un algorithme temps linéaire pour tester la vérité de certaines formules booléennes quantifiés ). Il peut apparemment être acheté en ligne pour environ 20 $ USD. Je ne sais pas si cela est utile ou non, mais il est!

Mise à jour: PDF gratuit du même document peut être trouvé ici . Le crédit va à Liori pour la trouver.

Answer 2

Ce fil entier est un peu foiré. Oui, on peut résoudre 2 sam. dans le temps linéaire, mais pas - vous ne pouvez pas le résoudre pour que de nombreuses variables. Le temps de résoudre 2-SAM. est linéaire par rapport au nombre de l'implication, qui pour 200 000 variables pourraient atteindre jusqu'à (200000 * 199999) / 2 et de plus si vous utilisez cette solution, vous aurez besoin d'environ la même quantité de mémoire . Il y a une autre solution (ne pas utiliser des composants fortement connectés qui est plus lent, mais n'a pas besoin que beaucoup de mémoire).