I'm going over past papers for my exam and I came across this question. The only time I have heard of "Not-All-Equal" was as a 3-Sat problem, so I'm wondering if this question does actually mean 2-Sat and if so, could you possibly explain?
I dont really want an answer, I'd much rather an explaination so that I can work it out for myself.
Question: We consider a special case of the Not-All-Equal 2-SAT problem where no literal contains a negation. The task is to decide if it i s possible to assign truth values to the variables such that each clause has one literal that is true and one that is false. Recall that 2-COL (or 2-Colourability) is the decision problem where the input is a graph and the task is to determine if the vertices can be coloured by 2 colours such that neighbouring vertices (vertices joint with an edge) have different colours.
a) Consider the Not-All-Equal 2-SAT problem given by the clauses
{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}
Are these clauses Not-All-Equal satisfiable? Explain why this problem is equivalent to a 2- COL problem.
Draw the graph for this 2-COL problem and explain why the graph not is 2-Colourable.
I assume your notation $\{x_i,x_j\}$ which you call a clause is just a set of two propositions $x_i$ and $x_j$ and that clause is called "not-all-equal" satisfiable provided one may assign truth values such that one of $x_i,x_j$ is T (true) and the other F (false).
Since it doesn't matter which is a true, it makes sense to draw this particular clause as a line segment connecting nodes $x_i$ and $x_j.$ In any given situation we make nodes for each proposition and connect any two that appear in the same clause. This is the connection to 2-colorability since if A,B colors denote T,F then the clause is not-all-equal satisfiable iff there is a two coloring such that no two nodes connected by a segment should be the same color.
In your specific problem mentioned, after drawing the five nodes and connecting the pairs which are in the same clause you get a cycle of length 5. The reason that can't be 2 colorable is that if you start out with say color B, the colors must alternate and you have B,A,B,A,B with B at the fifth node, but this node connects to the first node already colored B making it impossible to finish the coloring.
In general I guess any graph not having an odd length loop as a subgraph anywhere could be 2-colored, but that's just an initial intuition. Probably a proof could be found using a google on "two colored graphs" or the like.