Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Tang, Aoa | Wang, Xiaofenga; b; * | Peng, Qingyuana | Wang, Junxiaa | Yang, Yia | He, Feia | Hua, Yingyinga
Affiliations: [a] School of Computer Science and Engineering, North Minzu University, Yinchuan, China | [b] The Key Laboratory of Images & Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, Yinchuan, China
Correspondence: [*] Corresponding author. Xiaofeng Wang, School of Computer Science and Engineering, North Minzu University, NingXia, China. E-mail: [email protected].
Abstract: A CNF formula with each clause of length k and each variable occurring 4s times, where positive occurrences are 3s and negative occurrences are s, is a regular (3s + s, k)-CNF formula (F3s+s,k formula). The random regular exact (3s + 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 F3s+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 (3s + s, k)-SAT problem for k≥3. When s < s*, F3s+s,k formula is satisfiable with high probability; when s > s*, F3s+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.
Keywords: Random regular exact (3s + s, k)-SAT problem, first moment method, second moment method, small subgraph conditioning method, phase transition
DOI: 10.3233/JIFS-238254
Journal: Journal of Intelligent & Fuzzy Systems, vol. Pre-press, no. Pre-press, pp. 1-11, 2024
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]