Invitation to the Logic Seminar at the National University of Singapore
Date: Wednesday, 24 October 2018, 17:00 hrs
Room: S17#04-05, Department of Mathematics, NUS
Speaker: Frank Stephan
Title: A fast exponential time algorithm for Max Hamming Distance X3SAT
SAT is the problem which asks whether a given list of clauses in
n Boolean variables can be satisfied by an assignment
to the variables which is common for all clauses,
XSAT is the variant of SAT which asks the same, but requires in
addition that in each clause exactly one literal is true; X3SAT
is the corresponding problem with the additional constraint that
every clause contains up to three literals only. Now the problem
“Max Hamming Distance X3SAT” asks for the maximum
Hamming distance taken by two solutions of a given instance.
X3SAT can be solved only in exponential time, but the corresponding
exponential time algorithm is quite fast, an algorithm of Magnus
Wahlstroem from 2007 provides time O(1.0984^n).
The problem to find pairs of solutions of maximum Hamming distance
is more difficult: The up to now best known bound is by
Fu, Zhou and Yin of time O(1.6760^n) and the contribution
of the here presented work is to bring this down to O(1.3298^n).
This is joint work with Gordon Hoi and the paper is available
from the speaker’s homepage.