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.