Pergunta

One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor b)$, one from $\neg a$ to $b$ and one from $\neg b$ to $a$, respectively representing the implications $\neg a \implies b$ and $\neg b \implies a$. Finally, (assuming a solution exists) one sorts the connected components in topological order and traverses these in reverse order. Now for the important part :
For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.
Don't change variables already set. The resulting assignment is a solution.

My question is : Do other assignments work as well, as long as the underlying implications stay $true$ ? For example :
For every literal $a$ encountered, set variable $a = false$, and for every literal $\neg a$ encountered, set variable $a = true$.
since $false \implies false$, or even some combination :
For every literal $a$ encountered, if it points to some literal that equals $false$, set $a = false$, otherwise set it to either $false$ or $true$. For every literal $\neg a$ encountered, if it points to some literal that equals $false$, set $a = true$, otherwise set it to either $false$ or $true$.
since $true \implies true$, $false \implies true$, and $false \implies false$?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top