Frank Stephan: A fast exponential time algorithm for Max Hamming Distance X3SAT

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.