License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.17
URN: urn:nbn:de:0030-drops-115799
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11579/
Go to the corresponding LIPIcs Volume Portal

Hoi, Gordon ; Jain, Sanjay ; Stephan, Frank

A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT

pdf-format:
LIPIcs-FSTTCS-2019-17.pdf (0.5 MB)

Abstract

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 related question is to determine the maximal Hamming distance between two solutions of the instance. Dahllöf provided an algorithm for Maximum Hamming Distance XSAT, which is more complicated than the same problem for X3SAT, with a runtime of O(1.8348^n); Fu, Zhou and Yin considered Maximum Hamming Distance for X3SAT and found for this problem an algorithm with runtime O(1.6760^n). In this paper, we propose an algorithm in O(1.3298^n) time to solve the Max Hamming Distance X3SAT problem; the algorithm actually counts for each k the number of pairs of solutions which have Hamming Distance k.

BibTeX - Entry

@InProceedings{hoi_et_al:LIPIcs:2019:11579,
  author =	{Gordon Hoi and Sanjay Jain and Frank Stephan},
  title =	{{A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11579},
  URN =		{urn:nbn:de:0030-drops-115799},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.17},
  annote =	{Keywords: X3SAT Problem, Maximum Hamming Distance of Solutions, Exponential Time Algorithms, DPLL Algorithms}
}

Keywords: X3SAT Problem, Maximum Hamming Distance of Solutions, Exponential Time Algorithms, DPLL Algorithms
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI