Umsetzungsfragen in 2-Erfüllbarkeitsproblem

Question

Ich möchte für 100000 Literale 2-SAT Problem implementieren. So gäbe es 200000 Ecken sein. So bin ich stecken eine Reihe von allen erreichbaren Ecken von jedem Scheitelpunkt auf, die, Raum Komplexität O(200000^2), die so nicht machbar ist bitte eine Lösung dafür vorschlagen. Und bitte etwas Licht auf effiziente Umsetzung von 2-SAT Problem werfen.

Answer 1

wikipedia :

  

... 2-Erfüllbarkeit in Polynomialzeit gelöst werden. Als Aspvall, Plass & Tarjan (1979) beobachtet, eine 2-Erfüllbarkeit Instanz ist lösbar, wenn und nur wenn jede Variable der Instanz gehört zu einer anderen stark verbundenen Komponente der Implikation graph als die Negation der gleichen variablen. Da stark verbundene Komponenten in linearer Zeit können auf Tiefensuche, die gleiche lineare Zeit gebunden gilt auch für 2-Erfüllbarkeit.

Basis durch einen Algorithmus zu finden

Ich werde nicht so tun, als die meisten von diesem Absatz zu verstehen, aber es scheint, dass es ist einen Algorithmus, der verwendet werden kann, das 2-SAT Problem zu lösen, und es ist in diesem verweist beschrieben Dokument ( ein linearer Zeitalgorithmus, um die Wahrheit bestimmter quantifizieren boolesche Formeln für die Prüfung ). Es kann offenbar für etwa $ 20 USD online erworben werden. Ich bin nicht sicher, ob das hilfreich ist oder nicht, aber da ist es!

Update: Eine kostenlose PDF des gleichen Dokuments finden Sie hier . Kredit geht an Liori für die Entdeckung.

Answer 2

Dieser ganze Thread ist ein bisschen durcheinander. Ja, kann man 2-sat in linearer Zeit lösen, aber nein - man kann es nicht lösen für so viele Variablen. Die Zeit 2-sat zu lösen, ist linear in Bezug auf die Anzahl der Implikation, die für 200 000 Variablen erreichen konnte zu (200000 * 199999) / 2 und darüber hinaus, wenn Sie diese Lösung verwenden, werden Sie über die gleiche Menge an Speicher benötigen . Es gibt eine andere Lösung (nicht stark verbundenen Komponenten, die langsamer ist, aber muss nicht so viel Speicher).