View in EDS

Improved algorithms for the general exact satisfiability problem.

Saved in:
Bibliographic Details
Title: Improved algorithms for the general exact satisfiability problem.
Authors: Hoi, Gordon1 (AUTHOR) e0013185@u.nus.edu, Stephan, Frank1,2 (AUTHOR) fstephan@comp.nus.edu.sg
Source: Theoretical Computer Science. Oct2021, Vol. 889, p60-84. 25p.
Subjects: Algorithms, Polynomials, Polynomial time algorithms, Assignment problems (Programming)
Abstract: The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called G i XSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0 , 1 , ... , i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G i XSAT, for i ∈ { 2 , 3 , 4 } , in O (1.3674 n) time, O (1.5687 n) time and O (1.6545 n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O (1.4203 n) time for G2XSAT by Zhou, Jiang and Yin and from O (1.6202 n) time for G3XSAT by Dahllöf and from O (1.6844 n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O (1.3188 n) time, O (1.3407 n) time and O (1.3536 n) time respectively at the expense of using exponential space. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 152766030
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Improved algorithms for the general exact satisfiability problem.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Hoi%2C+Gordon%22">Hoi, Gordon</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> e0013185@u.nus.edu</i><br /><searchLink fieldCode="AR" term="%22Stephan%2C+Frank%22">Stephan, Frank</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> fstephan@comp.nus.edu.sg</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Oct2021, Vol. 889, p60-84. 25p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Assignment+problems+%28Programming%29%22">Assignment problems (Programming)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called G i XSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0 , 1 , ... , i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G i XSAT, for i ∈ { 2 , 3 , 4 } , in O (1.3674 n) time, O (1.5687 n) time and O (1.6545 n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O (1.4203 n) time for G2XSAT by Zhou, Jiang and Yin and from O (1.6202 n) time for G3XSAT by Dahllöf and from O (1.6844 n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O (1.3188 n) time, O (1.3407 n) time and O (1.3536 n) time respectively at the expense of using exponential space. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=152766030
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2021.07.036
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 25
        StartPage: 60
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Polynomials
        Type: general
      – SubjectFull: Polynomial time algorithms
        Type: general
      – SubjectFull: Assignment problems (Programming)
        Type: general
    Titles:
      – TitleFull: Improved algorithms for the general exact satisfiability problem.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Hoi, Gordon
      – PersonEntity:
          Name:
            NameFull: Stephan, Frank
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 08
              M: 10
              Text: Oct2021
              Type: published
              Y: 2021
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 889
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1