View in EDS HTML Full Text PDF Full Text

The phase transition in random regular exact (3 s  + s , k)-SAT problem.

Saved in:
Bibliographic Details
Title: The phase transition in random regular exact (3 s  + s , k)-SAT problem.
Authors: Tang, Ao1 (AUTHOR), Wang, Xiaofeng1,2 (AUTHOR) xfwang@nmu.edu.cn, Peng, Qingyuan1 (AUTHOR), Wang, Junxia1 (AUTHOR), Yang, Yi1 (AUTHOR), He, Fei1 (AUTHOR), Hua, Yingying1 (AUTHOR)
Source: Journal of Intelligent & Fuzzy Systems. Aug2025, Vol. 49 Issue 2, p340-350. 11p.
Subjects: Phase transitions, Satisfiability (Computer science), Empirical research, Mathematical proofs, Boolean expressions, Graph theory
Abstract: A CNF formula with each clause of length k and each variable occurring 4 s times, where positive occurrences are 3 s and negative occurrences are s, is a regular (3 s + s, k)-CNF formula (F 3 s + s, k formula). The random regular exact (3 s + s, k)-SAT problem is whether there exists a set of Boolean variable assignments such that exactly one literal is true for each clause in the F 3 s + s, k formula. By introducing a random instance generation model, the satisfiability phase transition of the solution is analyzed by using the first moment method, the second moment method, and the small subgraph conditioning method, which gives the phase transition point s* of the random regular exact (3 s + s, k)-SAT problem for k ≥3. When s < s*, F 3 s + s, k formula is satisfiable with high probability; when s > s*, F 3 s + s, k formula is unsatisfiable with high probability. Finally, through the experimental verification, the results show that the theoretical proofs are consistent with the experimental results. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Intelligent & Fuzzy Systems is the property of Sage Publications Inc. 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
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 187698586
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: The phase transition in random regular exact (3 s &#160;+ s , k)-SAT problem.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Tang%2C+Ao%22&quot;&gt;Tang, Ao&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Wang%2C+Xiaofeng%22&quot;&gt;Wang, Xiaofeng&lt;/searchLink&gt;&lt;relatesTo&gt;1,2&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; xfwang@nmu.edu.cn&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Peng%2C+Qingyuan%22&quot;&gt;Peng, Qingyuan&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Wang%2C+Junxia%22&quot;&gt;Wang, Junxia&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Yang%2C+Yi%22&quot;&gt;Yang, Yi&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22He%2C+Fei%22&quot;&gt;He, Fei&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Hua%2C+Yingying%22&quot;&gt;Hua, Yingying&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22Journal+of+Intelligent+%26+Fuzzy+Systems%22&quot;&gt;Journal of Intelligent &amp; Fuzzy Systems&lt;/searchLink&gt;. Aug2025, Vol. 49 Issue 2, p340-350. 11p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Phase+transitions%22&quot;&gt;Phase transitions&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Satisfiability+%28Computer+science%29%22&quot;&gt;Satisfiability (Computer science)&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Empirical+research%22&quot;&gt;Empirical research&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Mathematical+proofs%22&quot;&gt;Mathematical proofs&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Boolean+expressions%22&quot;&gt;Boolean expressions&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Graph+theory%22&quot;&gt;Graph theory&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: A CNF formula with each clause of length k and each variable occurring 4 s times, where positive occurrences are 3 s and negative occurrences are s, is a regular (3 s + s, k)-CNF formula (F 3 s + s, k formula). The random regular exact (3 s + s, k)-SAT problem is whether there exists a set of Boolean variable assignments such that exactly one literal is true for each clause in the F 3 s + s, k formula. By introducing a random instance generation model, the satisfiability phase transition of the solution is analyzed by using the first moment method, the second moment method, and the small subgraph conditioning method, which gives the phase transition point s* of the random regular exact (3 s + s, k)-SAT problem for k ≥3. When s &lt; s*, F 3 s + s, k formula is satisfiable with high probability; when s &gt; s*, F 3 s + s, k formula is unsatisfiable with high probability. Finally, through the experimental verification, the results show that the theoretical proofs are consistent with the experimental results. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of Journal of Intelligent &amp; Fuzzy Systems is the property of Sage Publications Inc. and its content may not be copied or emailed to multiple sites without the copyright holder&#39;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.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=187698586
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.3233/JIFS-238254
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 11
        StartPage: 340
    Subjects:
      – SubjectFull: Phase transitions
        Type: general
      – SubjectFull: Satisfiability (Computer science)
        Type: general
      – SubjectFull: Empirical research
        Type: general
      – SubjectFull: Mathematical proofs
        Type: general
      – SubjectFull: Boolean expressions
        Type: general
      – SubjectFull: Graph theory
        Type: general
    Titles:
      – TitleFull: The phase transition in random regular exact (3 s  + s , k)-SAT problem.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Tang, Ao
      – PersonEntity:
          Name:
            NameFull: Wang, Xiaofeng
      – PersonEntity:
          Name:
            NameFull: Peng, Qingyuan
      – PersonEntity:
          Name:
            NameFull: Wang, Junxia
      – PersonEntity:
          Name:
            NameFull: Yang, Yi
      – PersonEntity:
          Name:
            NameFull: He, Fei
      – PersonEntity:
          Name:
            NameFull: Hua, Yingying
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 08
              Text: Aug2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 10641246
          Numbering:
            – Type: volume
              Value: 49
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Journal of Intelligent & Fuzzy Systems
              Type: main
ResultId 1