# Unsatisfiable $X_3SAT$ Instances

Exactly $1$-in-$3$ SAT ($X_3SAT$) is a variant of the Boolean satisfiability problem. Given a set of clauses, each clause having three literals, is there a set of literals such that each clause contains exactly one literal from this set?

$X_3SAT$ is known to be $NP$-complete. It remains $NP$-Complete even when it is monotone (all literals are positive) and linear (no two clauses share more than one variable in common).

I am interested in finding short, unsatisfiable $X_3SAT$ instances. The shortest monotone linear $X_3SAT$ instance I have found so far is:

$(a,x_1,y_1)(a,x_2,y_2)(a,x_3,y_3)(x_1,x_2,x_3)(y_1,y_2,y_3)$

I think unsatisfiable monotone linear instances must have at least 4 loops. A loop is a sequence of clauses such that each clause shares one variable with the previous clause in the sequence, a different variable with the next clause, and doesn't share variables with any other clauses. The example above has six length three loops.

$(a,x_1,y_1)(a,x_2,y_2)(x_1,x_2,x_3)$

$(a,x_1,y_1)(a,x_3,y_3)(x_1,x_2,x_3)$

$(a,x_2,y_2)(a,x_3,y_3)(x_1,x_2,x_3)$

$(a,x_1,y_1)(a,x_2,y_2)(y_1,y_2,y_3)$

$(a,x_1,y_1)(a,x_3,y_3)(y_1,y_2,y_3)$

$(a,x_2,y_2)(a,x_3,y_3)(y_1,y_2,y_3)$

I am interested in short unsatisfiable instances. They don't have to be monotone.

• I am not sure what your question is ... but if you are asking if there is a smaller unsatisfiable monotone linear set, then the answer is no: the one you have is the shortest. – Bram28 Dec 30 '17 at 3:21
• I am looking for more examples of short unsatisfiable instances. – Russell Easterly Dec 30 '17 at 3:41