Complexité de la version de recherche de 2-SAT en supposant

Si , alors il y a un algorithme de logspace qui résout la version de décision de 2-SAT.$\mathsf{L = NL}$

• Est-il connu que implique qu'il existe un algorithme d'espace de journalisation pour obtenir une affectation satisfaisante , lorsqu'il reçoit une instance 2-SAT satisfaisante en entrée?$\mathsf{L = NL}$

• Sinon, qu'en est-il des algorithmes qui utilisent l'espace sub-linéaire (dans le nombre de clauses)?

Étant donné un 2-CNF satisfaisable , vous pouvez calculer une affectation satisfaisante particulière par une fonction NL (c'est-à-dire qu'il existe un prédicat NL qui vous indique si est vrai) . Une façon de le faire est décrite ci-dessous. J'utiliserai librement le fait que NL est fermé sous -reductions, donc les fonctions NL sont fermées sous composition; c'est une conséquence de NL = coNL.e P ( ϕ , i ) e ( x i ) A C$\phi$$e$$P(\phi,i)$$e(x_i)$$\mathrm{AC}^0$

Soit un 2-CNF satisfaisable. Pour tout littéral , soit a → le nombre de littéraux accessibles depuis a par un chemin dirigé dans le graphe d'implication de ϕ , et le nombre de littéraux à partir desquels est accessible. Les deux sont calculables en NL.a a $\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$

Observez que , et , en raison de la symétrie asymétrique du graphe d'implication. Définissez une affectation pour que$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• si , alors ;$a^\ot>a^\to$$e(a)=1$

• si , alors ;$a^\ot<a^\to$$e(a)=0$

• si , soit minimal tel que ou apparaisse dans la composante fortement connectée de (il ne peut pas être les deux, car est satisfaisable). Mettez si apparaît, et sinon.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

La symétrie asymétrique du graphique implique que , donc c'est une affectation bien définie. De plus, pour toute arête dans le graphe d'implication:$e(\ob a)=\ob{e(a)}$$a\to b$

• Si n'est pas accessible depuis , alors et . Ainsi, implique .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• Sinon, et sont dans le même composant fortement connecté, et , . Ainsi, .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Il s'ensuit que .$e(\phi)=1$