A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT

Gordon Hoi, Sanjay Jain, Frank Stephan

X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A…