Since your question is somewhat open ended, here's an observation, although it doesn't go anywhere yet.
A 2SAT instance is a decision problem in which given a set of variables $V$ and a formula comprising a conjunction of clauses over them, each clause being distinct and containing exactly two distinct literals, one wishes to know whether there is a truth assignment to the variables that makes the formula true.
Each 2SAT instance induces a digraph on $V cup overline{V}$: an arc from $u$ to $v$ exists if there is a clause $overline{u} lor v$.
Conjecture: If this digraph is a DAG, then the 2SAT instance must be satisfiable.
If the 2SAT instance is satisfiable then the digraph must have exactly one variable in each of its strongly connected components.
Moreover, such ``2SAT digraphs'' are transposable: reversing their arcs gives a digraph isomorphic to the original.
Your question could be interpreted as being about a collection of 2SAT instances where one is allowed to negate the literals in all the clauses of any instance.
No comments:
Post a Comment