The Phase Transition Analysis for the Random Regular Exact 2-(d, k)-SAT Problem

Abstract

In a regular ($d,k$)-CNF formula, each clause has length k and each variable appears d times. A regular structure such as this is symmetric, and the satisfiability problem of this symmetric structure is called the $(d,k)$-SAT problem for short. The regular exact 2-($d,k$)-SAT problem is that for a ($d,k$)-CNF formula F, if there is a truth assignment T, then exactly two literals of each clause in F are true. If the formula F contains only positive or negative literals, then there is a satisfiable assignment T with a size of $2n/k$ such that F is 2-exactly satisfiable. This paper introduces the ($d,k$)-SAT instance generation model, constructs the solution space, and employs the method of the first and second moments to present the phase transition point $d^{*}$ of the 2-($d,k$)-SAT instance with only positive literals. When $d<d^{*}$, the 2-($d,k$)-SAT instance can be satisfied with high probability. When $d>d^{*}$, the 2-($d,k$)-SAT instance can not be satisfied with high probability. Finally, the verification results demonstrate that the theoretical results are consistent with the experimental results.

1. Introduction

The satisfiability (SAT) problem of Boolean formula mainly investigates whether there is a satisfiable truth assignment for a given Conjunctive Normal Form (CNF) formula. As the first NP-complete problem to be proved, the SAT problem has been deeply studied for a long time. Various SAT problems with regular structure have been attracting increasing attention from scholars, such as limiting the length of clauses or the number of variables appearing. The SAT problem that limits the length of each clause to k is called a k-SAT problem. It has been proven that the k-SAT problem was hard to solve in the “worst” case. In recent years, some scholars have begun to study the SAT problem with symmetric structure. In this type of SAT problem, the number of occurrences of each variable is limited to d and the length of each clause is k. The results show that any k-SAT instance can be reduced to a ($d,k$)-SAT instance of this symmetric structure [1,2]. For the ($d,k$)-SAT problem, if there is a set of variable assignments such that exactly two literals in each clause of the ($d,k$)-SAT instance are true, such problem is called the regular exact 2-($d,k$)-SAT problem. This problem is still hard to solve in the “worst” case, and the study of it is helpful to further analyze other SAT problems with symmetric structure.

Studying SAT problems in some specific situations will help people to discover the general mathematical phenomena of SAT problems and design more effective algorithms for solving SAT problems. Currently, more studies focus on the random k-SAT problem. Experimental verification and theoretical analysis of this problem have shown that the clause constraint density $\alpha$ (the ratio of the number of clauses m to the number of variables n) of the CNF formula was an important parameter affecting the satisfiability and the difficulty of solving the formula [3,4,5,6]. It has been found that there was a critical value ${\alpha }_k$ associated with k. When $\alpha <{\alpha }_k$, the random k-SAT problem instance could be satisfied with a high probability. When $\alpha >{\alpha }_k$, the random k-SAT problem instance could not be satisfied with a high probability [3]. This sudden change from satisfied to unsatisfied was called the phase transition phenomenon of the k-SAT problem, and the corresponding critical value ${\alpha }_k$ was called the phase transition point. Additionally, it was also found that when $\alpha$ was far away from the phase transition point ${\alpha }_k$, the random k-SAT problem was easy to solve. When $\alpha$ was close to the phase transition point ${\alpha }_k$, the random k-SAT problem was challenging to solve. In the random 3-SAT problem, the research revealed that ${\alpha }_k$ was at least 3.52 [7] and at most 4.4898 [8]. In addition, the instances that most excellent SAT solvers could solve were closely related to $\alpha$. For instance, the DPLL algorithm was applicable to solve pure text random 3-SAT instances with constraint density $\alpha <1.6$, the Zchaff algorithm was suitable for dealing with random 3-SAT instances with clause constraint density $\alpha <3.52$ that had the most positive or negative literals, WalkSAT was suitable for solving random 3-SAT instances with clause constraint density $\alpha$ slightly higher than 3.95 [9], the Belief Propagation algorithm was suitable for random 3-SAT instances with clause constraint density $\alpha <3.95$, and the Survey Propagation algorithm was suitable for solving clause constraint density $\alpha <4.26$ random 3-SAT instances [10]. However, all symmetric ($d,k$)-SAT problems have the same clause constraint density, because in such formulas, each variable is copied d times to form the $dn$ variable junction points, each clause is copied k times to form the $km$ clause nodes, and $dn=km$. Obviously, it is not enough to characterize the satisfiability and difficulty of such a regular structure SAT problem only by the constraint density of clauses. To better investigate the difficulty of solving such SAT problems, new parameters should be introduced to characterize the structural features of the formulas.

The phase transition analysis of the SAT problem with symmetric structure has obtained abundant research results. Boufkhad et al. firstly proposed the regular ($d,k$)-SAT problem with this symmetric structure and pointed out that the satisfiable phase transition point of the random regular ($3,k$)-SAT problem was $2.46\le {\alpha }_{k,3}\le 3.78$ in [11]. On this basis, Rathi et al. obtained the upper and lower bounds of the phase transition points of the problem by using the method of first and second moments [12]. The authors provided the phase transition point of the random regular NAE-SAT problem and obtained a phase transition control parameter concerning parameter d [13]. Achlioptas et al. studied the phase transition of 1-in-k-SAT and NAE-3-SAT problems, and found that the upper and lower bounds of NAE-3-SAT were $1.514<c_{3,NAE}<2.215$ [14]. Then, the phase transition of the NAE-k-SAT problem was provided in [15]. The author proposed the random regular exact cover problem (exactly one in every clause is true), studied its satisfiable phase transition, and proved it by using the subgraph method [16]. Further, the phase transition of the exact problem was provided by using the method of differential equation [17]. Inspired by the exact problem, we propose to study the phase transition of the regular exact 2-($d,k$)-SAT problem, and find the phase transition control parameters for the problem.

This article introduces s-exact satisfiability. For a ($d,k$)-CNF formula F, if it contains only positive or negative literals, there is a satisfiable assignment T of size $sn/k$, such that F is s-exactly satisfiable. Then, we introduce the generation model of ($d,k$)-SAT instance, construct the solution space, and employ the method of the first-order moment and the second-order moment to present the phase transition point $d^{*}$ of the 2-($d,k$)-SAT problem. Specifically, let $k\ge 3$, for a positive integer d, $d^{*}=\left(2ln(2/k)+(k-2)ln(1-2/k)\right)/\left(ln(1-1/k)\right.$$+\left(k-2\right)\left.ln(1-2/k)\right)$. When $d<d^{*}$, the problem is satisfiable with high probability. When $d>d^{*}$, the problem is unsatisfiable with high probability. Since the phase transition point $d^{*}$ is a function of the clause length k, we take the three cases of $k=4$, $k=6$, and $k=7$ respectively, and choose ($d,k$)-SAT instance with a scale of $n=10$ and $n=20$ to conduct experiments. The verification results demonstrate that the theoretical results are in agreement with the experimental results.

2. Preliminaries

2.1. Random Regular Exact 2-($d,k$)-SAT Problem

A literal is a propositional variable x or a negation of a propositional variable $\neg x$. A clause C is the disjunction of several literals ($C=(L_1\vee$…$\vee L_k)$ ), the clause C can be regarded as the set of literals ($C=\{L_1,$…$,L_k\}$ ), k denotes the length of the clause, and $Var\left(C_j\right)$ represents the set of variables in a clause $C_j$. A Conjunction Normal Form (CNF) formula F is the conjunction of several clauses ($F=(C_1\wedge$…$\wedge C_m)$ ), and the formula can be regarded as a set of clauses $F=\{C_1,$…$,C_m\}$, or a clause table $F=[C_1,$…$,C_m]$, where m is the size of the formula and $\mathrm{var}\left(F\right)$ represents the set of variables appearing in formula F. $\#\mathrm{var}\left(F\right)$ and $\#cl\left(F\right)$ are the number of variables and clauses appearing in formula F, respectively. The number of occurrences of a variable x refers to the sum of the corresponding positive and negative literals, denoted as $occs(x,F)$, using $pos(x,F)$ and $neg(x,F)$ respectively, to represent the positive and negative occurrence times of the variable x in F, and signify $occ(x,F)=pos(x,F)+neg(x,F)$. A regular ($d,k$)-CNF formula means that in the CNF formula F, each variable occurs exactly d times, and the length of each clause is exactly k. The regular structure is symmetric. In the current formula class, there must be $km=dn$.

For any CNF formula F, if there is a truth assignment on the set of variables $\left\{x_1,x_2,\dots ,x_n\right\}$ that makes the value of formula F be TRUE, then F is satisfiable (SAT). If the value of F is FALSE due to $2^n$ different assignments of n Boolean variables, then formula F is unsatisfiable (UNSAT). The satisfiability problem of symmetric structures is called the $(d,k)$-SAT problem.

Definition 1.

Let F be a ($d,k$)-CNF formula with n variables $\left\{x_1,x_2,\dots ,x_n\right\}$, and m clauses $\left\{C_1,C_2,\dots ,C_m\right\}$. It is said that formula F is s-exactly satisfiable. If there is a truth value assignment T, each clause $C_j$ has exactly s literals to be true, where $1\le s<k$.

Note: a formula can be satisfied, but it does not have to be s-exactly satisfied.

Suppose F is a ($d,k$)-CNF formula with only positive literals or only negative literals and T is a satisfying assignment, for each clause $C_j$, if $\left|T\cap C_j\right|=s$, then $d\left|T\right|=mk-m(k-s)=sm=sd·\left(n/k\right)$. Thus, $\left|T\right|=sn/k$. According to the above derivation, for any ($d,k$)-CNF formula F containing only positive literals or only negative literals, if F is s-exactly satisfiable, then F must have a satisfiable assignment with a size of $sn/k$. However, for the ($d,k$)-CNF formula with both positive and negative literals, there is no such property.

Theorem 1.

Let the formula F be a regular ($d,k$)-CNF formula with n variables and m clauses. If F contains only positive or negative literals, then there is a satisfiable assignment T of size $sn/k$, such that F is s-exactly satisfiable.

Proof. 

Since the formula F is a regular ($d,k$)-CNF formula, each variable appears d times, and the length of each clause is k. Let a satisfiable assignment $T=\left\{x_1,x_2,\dots ,x_{sn/k}\right\}$. Since $km=dn$, then $d\left|T\right|=d·\left(sn/k\right)=s·\left(dn/k\right)=s·\left(mk/k\right)=sm$. Therefore, we take all $sn/k$ variables as positive literals or negative literals, and equally distribute them to m clauses. Thus, the formula F is s-exactly satisfiable. □

The following figure (Figure 1) is a regular (4,3)-CNF formula, where $n=6$ and $m=8$. The formula is 2-exactly satisfiable, and $T=\left(x_1,x_2,x_3,x_5\right)$ is a satisfiable assignment of it.

Therefore, we discuss the 2-exactly satisfiable problem of the ($d,k$)-CNF formula with only positive literals, in order to further analyze and understand the degree of difficulty and phase transition law of the s-($d,k$)-SAT problem.

2.2. Random Regular ($d,k$)-SAT Instance Generation Model

Let the set of variables $V=\left\{x_1,x_2,\dots ,x_n\right\}$, and copy each variable in V d times to produce the following variable matrix:

$$V^{*}=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \dots & x_{1,d}\\ x_{2,1}& x_{2,2}& \dots & x_{2,d}\\ ⋮& & & \\ x_{n,1}& x_{n,2}& \dots & x_{n,d}\end{array}\right).$$

Let the CNF formula $F=(C_1\wedge$…$\wedge C_m)$, and copy each clause in F k times to produce the following matrix, which is called the position matrix of argument placement (short for position matrix):

$$F^{*}=\left(\begin{array}{cccc}{C}_{1,1}& C_{1,2}& \cdots & C_{1,k}\\ C_{2,1}& C_{2,2}& \cdots & C_{2,k}\\ ⋮& & & \\ C_{m,1}& C_{m,2}& \cdots & C_{m,k}\end{array}\right).$$

Note: for a regular ($d,k$)-CNF formula, $km=dn$.

All permutations on the set $\left\{1,2,\dots ,mk\right\}$ constitute the sample space, and there are $\left(mk\right)!$ permutations in total. Randomly take a permutation $\pi$ from it, corresponding to the generation of a regular $(d,k)$-bipartite graph $G=\left(U,V,E\right)$, where the relationship between the edges is as follows: $\pi \left(x_{i,p}\right)=C_{j,q}\iff x_i\in C_j$. Since a permutation determines an instance, the size of the formula instance space is $\left(mk\right)!$.

2.3. Phase Change Analysis Technique

This section mainly introduces phase transitions and some methods used in phase transitions.

Definition 2.

Suppose a model M, a property Q, and a probability function $p:N\to \left[0,1\right]$, if there are two probability functions satisfying the following conditions [18]:

(1) 

When $\underset{n\to \infty }{lim}{p}_0\left(n\right)/p\left(n\right)=0$, almost certainly model M does not have property Q.

(2) 

When $\underset{n\to \infty }{lim}{p}_{\infty }\left(n\right)/p\left(n\right)=\infty$, almost certainly model M has property Q.

Then, the property Q has a phase change, and the function is called criticality (or threshold).

Suppose Q is a property with a phase transition property, then the probability function $p:N\to \left[0,1\right]$ is called strict criticality. If for any $c<1$, for almost all n, model M has no property Q. For any $c>1$, for almost all n, the model M has property Q.

In the proof of the phase transition phenomenon of the SAT problem, the first moment method is usually used to demonstrate that the SAT problem can satisfy the upper bound of the critical value. At the same time, the second moment method is used to prove that the SAT problem can satisfy the lower bound of the critical value.

The first moment method is a simple application of Markov’s inequality.

Theorem 2.

(Markov’s inequality [19]): Let Z be a random variable whose value is a non-negative integer, then for any real number, $\nu >0$:

$$Pr(Z\ge \nu )\le \frac{E\left[Z\right]}{\nu }.$$

It is of note that the value of Z is only a non-negative integer. According to Markov’s inequality, the probability of a random variable $Z\ge 1$ (i.e., $Z>0$) is at most $E\left(Z\right)$, that is, $Pr(Z\ge 1)\le E\left[Z\right]$.

The second moment method is an inequality which is directly derived from Chebyshev’s inequality.

Theorem 3.

(The second moment method [19]): Let Z be a random variable of non-negative integer value only, then:

$$Pr(Z=0)\le \frac{E\left[Z^2\right]}{E{\left[Z\right]}^2}.$$

3. Main Results

The phase transition phenomenon is one of the important characteristics of SAT problems. The study of this phenomenon will help to further understand the properties of SAT problems and design more efficient algorithms. In this section, the phase transition points of the 2-($d,k$)-SAT problem with symmetric structure are obtained by using the method of first and second moments.

Theorem 4.

Suppose F is a random regular exact 2-($d,k$)-SAT instance, and

$$d^{*}=\frac{2ln(\frac{2}{k})+(k-2)ln(1-\frac{2}{k})}{ln(1-\frac{1}{k})+(k-2)ln(1-\frac{2}{k})}.$$

When $k\ge 3$, for any positive integer d:

$$\underset{n\to \infty }{lim}Pr\left[Fissatisfiable\right]=\left\{\begin{array}{cc}1& d<d^{*}\\ 0& d>d^{*}.\end{array}\right.$$

Theorem 4 shows that for a 2-($d,k$)-SAT instance F, when $k\ge 3$, if $d<d^{*}$, then the high probability of F is satisfied. If $d>d^{*}$, then the high probability of F is not satisfied. Theorem 4 can be proved by the following two lemmas.

Lemma 1.

Suppose F is a random regular exact 2-($d,k$)-SAT instance. When $k\ge 3$, if $d>d^{*}$, F is unsatisfied with high probability.

Proof. 

Let $F=\left\{C_1,C_2,\dots ,C_m\right\}$ be a regular ($d,k$)-SAT instance, let $V=\left\{x_1,x_2,\dots ,x_n\right\}$ be a set of variables of instance F, and let T be a truth assignment on the set of variables V. Each clause $C_j$ in F satisfies $|T\cap C_j|=2$. Therefore, for each clause $C_j$, there are $\left(k-2\right)$ variables that are not entered in T. Since each variable occurs d times and $km=dn$, then $d\left|T\right|=mk-m\left(k-2\right)=2m=2dn/k$. Thus, $\left|T\right|=2n/k$.

Let $T=\left(x_1,x_2,\dots ,x_{2n/k}\right)$, copy d times, and generate the following matrix:

$$T^{\prime }=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \dots & x_{1,d}\\ x_{2,1}& x_{2,2}& \dots & x_{2,d}\\ ⋮& & & \\ x_{\frac{2n}{k},1}& x_{\frac{2n}{k},2}& \dots & x_{\frac{2n}{k},d}\end{array}\right).$$

There are $\frac{2n}{k}·d=2m$ variables in the matrix $T^{\prime }$, and the $2m$ variables are divided into m groups with 2 elements in each group. There are $\left(C_{2m}^2·C_{2m-2}^2\cdots C_4^2·C_2^2\right)/m!=\left(2m\right)!/\left(m!·2^m\right)$ possibilities for such a division. Since there are k positions in each row of formula F, there are $\left[\left(2m\right)!/\left(m!·2^m\right)\right]·m!·\left[{\left(k\left(k-1\right)\right)}^m/2^m\right]$ substitutions by replacing any two positions with the variables in matrix $T^{\prime }$. There are $(k-2)$ empty positions in each row of formula F after the substitution, which can be replaced by other remaining variables in V. There are $\left[m\right(k-2\left)\right]!$ possibilities for such a substitution. Therefore, the number of formulas that T satisfies is $\left[\left(2m\right)!/2^m\right]·\left[{\left(k\left(k-1\right)\right)}^m/2^m\right]·\left[m\left(k-2\right)\right]!$ in total. Thus, the number satisfying the formula in the instance space is $C_n^{2n/\phantom{2nk}k}·\left[\left(2m\right)!/2^m\right]·\left[{\left(k\left(k-1\right)\right)}^m/2^m\right]·\left[m(k-2)\right]!$.

Assuming that the instance F is uniformly and randomly selected in the instance space which the size is $\left(mk\right)!$, and the random variable $Z\left(n\right)$ is used to represent the number of satisfying solutions of F, the mathematical expectation of $Z\left(n\right)$ is expressed as follows:

$$E\left[Z\left(n\right)\right]=\frac{C_n^{2n/k}·\frac{\left(2m\right)!}{2^m}·\frac{{\left[k\right(k-1\left)\right]}^m}{2^m}·\left[m(k-2)\right]!}{\left(mk\right)!}.$$

According to the first moment, the task now is to prove that $\underset{n\to \infty }{lim}E\left[Z\left(n\right)\right]=0$. Firstly, $E\left[Z\right(n\left)\right]$ is simplified by the combined approximate formula: $C_n^{\alpha n}\approx \left[1/{\left(2\pi n\alpha \left(1-\alpha \right)\right)}^{1/2}\right]$$exp\left[nH\left(\alpha \right)\right],(0<\alpha <1)$.

$$\begin{array}{cc}\hfill E\left[Z\left(n\right)\right]& =\frac{C_n^{\frac{2n}{k}}·\frac{\left(2m\right)!}{2^m}·\frac{{\left(k\right(k-1\left)\right)}^m}{2^m}·\left(m(k-2)\right)!}{\left(mk\right)!}\hfill \\ & =\frac{k^m·{(k-1)}^m}{2^{2m}}·\frac{C_n^{\frac{2n}{k}}}{C_{mk}^{2m}}\hfill \\ & =2^{-2m}·k^m·{(k-1)}^m·\sqrt{\frac{2\pi mk\left(\frac{2}{k}\right)\left(1-\frac{2}{k}\right)}{2\pi n\left(\frac{2}{k}\right)\left(1-\frac{2}{k}\right)}}·e^{\left(n-mk\right)H\left(\frac{2}{k}\right)}\hfill \\ & =\sqrt{d}·e^{mlnk+mln\left(k-1\right)-2mln2+\left(n-mk\right)H\left(\frac{2}{k}\right)}\hfill \\ & =\sqrt{d}·e^{n\left(\frac{d}{k}lnk+\frac{d}{k}ln\left(k-1\right)-\frac{2d}{k}ln2+\left(1-d\right)H\left(\frac{2}{k}\right)\right)}\hfill \\ & =\sqrt{d}{e}^{n\phi \left(d\right)},\hfill \end{array}$$

where $\phi \left(d\right)=\left(d/k\right)lnk+\left(d/k\right)ln\left(k-1\right)-\left(2d/k\right)ln2+\left(1-d\right)H\left(2/k\right)$ and $H\left(\alpha \right)=-\alpha ln\left(\alpha \right)-(1-\alpha )ln(1-\alpha )$ is the entropy function.

To further simplify the processing of $\phi \left(d\right)$:

$$\begin{array}{cc}\hfill \phi \left(d\right)& =\frac{d}{k}lnk+\frac{d}{k}ln\left(k-1\right)-\frac{2d}{k}ln2+\left(1-d\right)H\left(\frac{2}{k}\right)\hfill \\ & =\frac{d}{k}\left(lnk+ln(k-1)-2ln2+2ln\left(\frac{2}{k}\right)+(k-2)ln(1-\frac{2}{k})\right)+H\left(\frac{2}{k}\right)\hfill \\ & =d\left(\frac{1}{k}ln(1-\frac{1}{k})+\frac{k-2}{k}ln(1-\frac{2}{k})\right)+H\left(\frac{2}{k}\right).\hfill \end{array}$$

Obviously, when $k\ge 3$, the function is a monotonically decreasing function of d, and has a unique zero:

$$d^{*}=\frac{2ln\left(\frac{2}{k}\right)+(k-2)ln(1-\frac{2}{k})}{ln(1-\frac{1}{k})+(k-2)ln(1-\frac{2}{k})}.$$

Therefore, when $k\ge 3$, $d>d^{*}$, $\underset{n\to \infty }{lim}E\left[Z\left(n\right)\right]=0$. Then:

$$\underset{n\to \infty }{Pr}[Z\left(n\right)\ge 1]=0.$$

In other words, when $k\ge 3$, $d>d^{*}$, the regular exact 2-($d,k$)-SAT instances are unsatisfied with high probability. □

Lemma 2.

Let F be a random regular exact 2-($d,k$)-SAT instance. When $k\ge 3$, if $d<d^{*}$, then F can be satisfied with high probability.

Proof. 

The following is mainly performed to calculate the value of $E\left[Z^2\left(n\right)\right]$. Suppose F is a satisfiable instance and has a satisfiable assignment set $\left\{T_1,T_2,\cdots ,T_r\right\}$ with r elements. Suppose a pair of assignments $(T_p,T_q)$ satisfy F, if and only if $T_p$ and $T_q$ satisfy F. Consider the set of assignment pairs $\{(T_p,T_q):1\le p,q\le r\}$ on $\left\{T_1,T_2,\cdots ,T_r\right\}$,, and the number of assignment pairs is $r^2$. Assume $T_{pq}=(T_p,T_q)$, then, the assignment pair can be expressed as the following matrix:

$$T^{*}=\left(\begin{array}{cccc}{T}_{11}& T_{12}& \cdots & T_{1r}\\ T_{21}& T_{22}& \cdots & T_{2r}\\ ⋮& ⋮& ⋮& ⋮\\ T_{r1}& T_{r2}& \cdots & T_{rr}\end{array}\right).$$

For the ($d,k$)-CNF formula, the size of any 2-exact satisfiable assignment T is $2n/\phantom{2nk}k$. The matrix $T^{\prime }$ is obtained by copying the variables in T d times. We write the matrix as set $T^{\prime }=\{x_{i,j}:1\le i\le 2n/k,1\le j\le d\}$. By pairing $\left(2n/k\right)·d=2m$ elements in $T^{\prime }$, the set of element pairs $T^{″}$ is constructed, and the size of the set $T^{\prime \prime }$ is m. Such set has $\left(C_{2m}^2·C_{2m-2}^2\cdots C_4^2·C_2^2\right)=\left(2m\right)!/\left(m!·2^m\right)$.

For any assignment pair $(T_p,T_q)$, the relationship is as follows:

$$\left|T_p-T_q\right|=\left|T_q-T_p\right|,0\le \left|T_p\cap T_q\right|\le \frac{2n}{k},0\le \left|T_p-T_q\right|\le \frac{2n}{k}.$$

Therefore, the size of the set difference can be used to divide the set $\{(T_p,T_q)|1\le p,q\le r\}$. When $\left|T_p-T_q\right|=\left|T_l-T_h\right|=\lambda$, $(T_p,T_q)$ and $(T_l,T_h)$ are in the same class, denoted as:

$$P_{\lambda }=\{(T_p,T_q):|T_p-T_q|=\lambda \}.$$

It can be seen that $P_0,P_1,\cdots ,P_{2n/k}$ forms a partition of $\{(T_p,T_q)|1\le p,q\le r\}$ and has:

$$\left|P_0\right|+\left|P_1\right|+\cdots +\left|P_{2n/k}\right|=r^2.$$

In a partition block $P_{\lambda }$, $\left|T_p-T_q\right|=\left|T_q-T_p\right|=\lambda$, $|T_p\cap T_q|=2n/k-\lambda$, the total number of variables involved is $2n/k+\lambda$. Introduce a normalization parameter: $0\le \omega \le 1$, and express the sum as an integral. Mark the division as follows:

$$Q_{\omega }=P_{\frac{2\omega n}{k}}=\{(T_p,T_q):|T_p-T_q|=\frac{2\omega n}{k}\}.$$

The set pair $(T_p,T_q)$ in the $Q_{\omega }$ block satisfies the following conditions:

$$|T_p-T_q|=|T_q-T_p|=\frac{2\omega n}{k},|T_p\cap T_q|=\frac{2(1-\omega )n}{k},|T_p\cup T_q|=\frac{2(1+\omega )n}{k}.$$

Taking a pair of satisfiable assignments as an example, the number of satisfiable formulas is calculated by the cross-assignment method. Let $T_p=\{x_1,\cdots ,x_{2\omega n/\phantom{2\omega nk}k},x_{2\omega n/\phantom{2\omega nk}k+1},\cdots ,x_{2n/k}\}$ and $T_q=\{x_{2\omega n/k+1},\cdots ,x_{2n/k},x_{2n/k+1},\cdots ,$ $x_{2(1+\omega )n/k}\}$. Then, $T_p-T_q=\{x_1,\cdots ,x_{2\omega n/\phantom{2\omega nk}k}\}$, $T_p\cap T_q=\{x_{2\omega n/k+1},\cdots ,x_{2n/k}\}$, $T_q-T_p=\{x_{2n/k+1},\cdots ,x_{2(1+\omega )n/k}\}$ and $\overline{T_p\cup T_q}=\{x_{2(1+\omega )n/k+1},\cdots ,x_n\}$. After the elements of these four parts are copied d times, the matrices A, B, C, and D are constructed:

$$A=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \cdots & x_{1,d}\\ x_{2,1}& x_{2,2}& \cdots & x_{2,d}\\ ⋮& ⋮& ⋮& ⋮\\ x_{\frac{2\omega n}{k},1}& x_{\frac{2\omega n}{k},2}& \cdots & x_{\frac{2\omega n}{k},d}\end{array}\right),D=\left(\begin{array}{cccc}{x}_{\frac{2\left(1+\omega \right)n}{k}+1,1}& x_{\frac{2\left(1+\omega \right)n}{k}+1,2}& \cdots & x_{\frac{2\left(1+\omega \right)n}{k}+1,d}\\ x_{\frac{2\left(1+\omega \right)n}{k}+2,1}& x_{\frac{2\left(1+\omega \right)n}{k}+2,2}& \cdots & x_{\frac{2\left(1+\omega \right)n}{k}+2,d}\\ ⋮& ⋮& ⋮& ⋮\\ x_{n,1}& x_{n,2}& \cdots & x_{n,d}\end{array}\right).$$

$$B=\left(\begin{array}{cccc}{x}_{\frac{2\omega n}{k}+1,1}& x_{\frac{2\omega n}{k}+1,2}& \cdots & x_{\frac{2\omega n}{k}+1,d}\\ x_{\frac{2\omega n}{k}+2,1}& x_{\frac{2\omega n}{k}+2,2}& \cdots & x_{\frac{2\omega n}{k}+2,d}\\ ⋮& ⋮& ⋮& ⋮\\ x_{\frac{2n}{k},1}& x_{\frac{2n}{k},2}& \cdots & x_{\frac{2n}{k},d}\end{array}\right),C=\left(\begin{array}{cccc}{x}_{\frac{2n}{k}+1,1}& x_{\frac{2n}{k}+1,2}& \cdots & x_{\frac{2n}{k}+1,d}\\ x_{\frac{2n}{k}+2,1}& x_{\frac{2n}{k}+2,2}& \cdots & x_{\frac{2n}{k}+2,d}\\ ⋮& ⋮& ⋮& ⋮\\ x_{\frac{2\left(1+\omega \right)n}{k},1}& x_{\frac{2\left(1+\omega \right)n}{k},2}& \cdots & x_{\frac{2\left(1+\omega \right)n}{k},d}\end{array}\right).$$

For each clause $C_j$ in ($d,k$)-CNF instance F, there is $|C_j\cap T|=2$. According to the cross-assignment method, there are several cases, as follows:

(1) The matrix A matches $\left(\omega n/k\right)·d=\omega m$ clauses in m clauses, corresponds to $\omega m$ rows in the position matrix, and occupies two positions in each row.

(2) The matrix B matches $(1-\omega )m$ clauses in m clauses, corresponds to $(1-\omega )m$ rows in the position matrix, and occupies two positions in each row.

(3) The matrix C matches $\left(\omega n/k\right)·d=\omega m$ clauses in m clauses, corresponds to $\omega m$ rows in the position matrix, and occupies two positions in each row.

For cases (1) and (3), which are jointly allocated to each row of the $\omega m$ row and match the four positions in the position matrix, there are a total of $\left(\omega m\right)!·{\left(C_k^2\right)}^{\omega m}·\left(\omega m\right)!·{\left(C_{k-2}^2\right)}^{\omega m}$ matches. Since $|C_j\cap T|=2$, in case (2), if the two elements in $\{x_i,x_j\}$ are both in $T_p\cap T_q$, then there are a total of $\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}$ matches. If one of the elements in $\{x_i,x_j\}$ is in $T_p\cap T_q$, then there are a total of $\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}·{\left(k-2\right)}^{(1-\omega )m}$ matches. Furthermore, the variables $\{x_i,x_j\}$, both in $T_p\cap T_q$ and one of them in $T_p\cap T_q$, are two mutually exclusive events. Therefore, in case (2), there are at least $\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}$ types of matches, and at most $\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}·{\left(k-2\right)}^{(1-\omega )m}$ types of matches. Through the above-mentioned matching, at most, $(1-\omega )m·(k-2)+\omega m·(k-4)=m(k-2-2\omega )$ positions remain unmatched. Thus, there are $\left[m(k-2-2\omega )\right]!$ matches in total.

For each satisfied assignment $T_p$, it can construct $\left(2m\right)!/\left(m!·2^m\right)$ elements. Thus, the formula can be satisfied as follows:

$$\begin{array}{c}\frac{\left(2m\right)!}{m!·2^m}·\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}·{\left(k-2\right)}^{(1-\omega )m}·\left(\omega m\right)!·{\left(C_k^2\right)}^{\omega m}·\left(\omega m\right)!·{\left(C_{k-2}^2\right)}^{\omega m}·\left[m(k-2-2\omega )\right]!.\hfill \end{array}$$

Therefore, for a given assignment pair $(T_p,T_q)$, the total number of formulas that $(T_p,T_q)$ can satisfy is:

$$\begin{array}{c}{C}_m^{\omega m}·\frac{\left(2m\right)!}{m!·2^m}·\left[(1-\omega )m\right]!·{\left(C_k^2\right)}^{(1-\omega )m}·{\left(k-2\right)}^{(1-\omega )m}·\left(\omega m\right)!·{\left(C_k^2\right)}^{\omega m}·\left(\omega m\right)!·{\left(C_{k-2}^2\right)}^{\omega m}·\left[m(k-2-2\omega )\right]!\hfill \\ =\frac{\left(2m\right)!}{m!·2^m}·m!·\left(\omega m\right)!·\left[m(k-2-2\omega )\right]!·\frac{k^m{(k-1)}^m}{2^m}·\frac{{(k-2)}^{\omega m}{(k-3)}^{\omega m}}{2^{\omega m}}·{(k-2)}^{(1-\omega )m}\hfill \\ =\frac{\left(2m\right)!·\left(\omega m\right)!·\left[m(k-2-2\omega )\right]!·k^m{(k-1)}^m{(k-2)}^m{(k-3)}^{\omega m}}{2^{(2+\omega )m}}.\hfill \end{array}$$

So, the maximum number of formulas satisfied by the assignment pair in $Q_{\omega }$ is:

$$|Q_{\omega }|\frac{\left(2m\right)!·\left(\omega m\right)!·\left[m(k-2-2\omega )\right]!·k^m{(k-1)}^m{(k-2)}^m{(k-3)}^{\omega m}}{2^{(2+\omega )m}}.$$

Specify a set S of size $2n/k$, and let $S^{\prime }$ and S satisfy the following conditions:

$$|S^{\prime }|=\frac{2n}{k},|S-S^{\prime }|=|S^{\prime }-S|=\frac{2\omega n}{k}.$$

Such subsets $S^{\prime }$ have:

$$C_{2n/k}^{2(1-\omega )n/k}·C_{n-2n/k}^{2\omega n/k}=C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}.$$

Then, the maximum number of formulas satisfied by all assignment pairs in $Q_{\omega }$ is:

$$\begin{array}{c}{C}_n^{2n/k}·C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}·\frac{\left(2m\right)!·\left(\omega m\right)!·\left[m(k-2-2\omega )\right]!·k^m{(k-1)}^m{(k-2)}^m{(k-3)}^{\omega m}}{2^{(2+\omega )m}}.\hfill \end{array}$$

Let $Z_{\omega }\left(n\right)$ denote the number of randomly selected formulas satisfied by the assignment pairs in $Q_{\omega }$, then:

$$\begin{array}{cc}\hfill E\left[Z_{\omega }\left(n\right)\right]& \le \frac{C_n^{2n/k}·C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}·\left(\left(2m\right)!\right)·\left(\omega m\right)!·\left(m(k-2-2\omega )\right)!·k^m{(k-1)}^m{(k-2)}^m{(k-3)}^{\omega m}}{2^{(2+\omega )m}·\left(mk\right)!}\hfill \\ & =E\left[Z\left(n\right)\right]·\frac{C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}·\left(\omega m\right)!·\left(m(k-2-2\omega )\right)!·{(k-2)}^m{(k-3)}^{\omega m}}{2^{\omega m}·\left(m(k-2)\right)!}\hfill \\ & \approx E\left[Z\left(n\right)\right]·\frac{C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}·{(k-2)}^m{(k-3)}^{\omega m}}{2^{\omega m}·C_{m(k-2)}^{\omega m}}.\hfill \end{array}$$

Based on the combined approximate formula, it is simplified as follows:

$$\begin{array}{cc}\hfill \frac{C_{2n/k}^{2\omega n/k}·C_{n-2n/k}^{2\omega n/k}}{C_{m(k-2)}^{\omega m}}& =\frac{\sqrt{\omega m(1-\frac{\omega }{k-2})}}{\sqrt{2\pi \frac{2n}{k}\omega (1-\omega )·\frac{2n}{k}\omega (1-\frac{2\omega }{k-2})}}·e^{\frac{2n}{k}H\left(\omega \right)+\frac{n}{k}\left(k-2\right)H\left(\frac{2\omega }{k-2}\right)-m\left(k-2\right)H\left(\frac{\omega }{k-2}\right)}\hfill \\ & \approx \frac{\sqrt{d}}{\sqrt{4\pi \frac{2n}{k}\omega (1-\omega )}}·e^{\frac{n}{k}\left(2H\left(\omega \right)+\left(k-2\right)H\left(\frac{2\omega }{k-2}\right)-d\left(k-2\right)H\left(\frac{\omega }{k-2}\right)\right)}.\hfill \end{array}$$

Therefore,

$$\begin{array}{cc}\hfill E\left[Z_{\omega }\left(n\right)\right]& \approx E\left[Z\left(n\right)\right]·\frac{{(k-2)}^m{(k-3)}^{\omega m}}{2^{\omega m}}·\frac{\sqrt{d}}{\sqrt{4\pi \frac{2n}{k}\omega (1-\omega )}}·e^{\frac{n}{k}\left(2H\left(\omega \right)+\left(k-2\right)H\left(\frac{2\omega }{k-2}\right)-d\left(k-2\right)H\left(\frac{\omega }{k-2}\right)\right)}\hfill \\ & =E\left[Z\left(n\right)\right]·\frac{\sqrt{d}}{\sqrt{4\pi \frac{2n}{k}\omega (1-\omega )}}·e^{\frac{n}{k}\left(2H\left(\omega \right)+\left(k-2\right)H\left(\frac{2\omega }{k-2}\right)-d\left(k-2\right)H\left(\frac{\omega }{k-2}\right)+dln\left(k-2\right)+\omega dln\left(k-3\right)-\omega dln2\right)}.\hfill \end{array}$$

and $E\left[Z^2\left(n\right)\right]={\sum }_{j=0}^{2n/k}E\left[Z_{\left(k/2n\right)·j}\left(n\right)\right]=E\left[Z\left(n\right)\right]+{\sum }_{j=1}^{2n/k}E\left[Z_{\left(k/2n\right)·j}\left(n\right)\right]$. Replace $kj/2n$ with ${\omega }_j$, as follows:

$$\begin{array}{cc}\hfill E\left[Z^2\left(n\right)\right]& =E\left[Z\left(n\right)\right]+{\displaystyle \sum _{j=1}^{2n/k}}E\left[Z_{{\omega }_j}\left(n\right)\right]\hfill \\ & \approx E\left[Z\left(n\right)\right]\left(1+{\displaystyle \sum _{j=1}^{2n/k}}\frac{\sqrt{d}}{\sqrt{4\pi \frac{2n}{k}{\omega }_j(1-{\omega }_j)}}·e^{n\psi \left({\omega }_j\right)}\right)\hfill \\ & =E^2\left[Z\left(n\right)\right]\left(\frac{1}{\sqrt{d}}{e}^{-n\phi \left(d\right)}+e^{-n\phi \left(d\right)}{\displaystyle \sum _{j=1}^{2n/k}}\frac{1}{\sqrt{4\pi \frac{2n}{k}{\omega }_j\left(1-{\omega }_j\right)}}{e}^{n\psi \left({\omega }_j\right)}\right),\hfill \end{array}$$

where $\psi \left({\omega }_j\right)=\left(2/k\right)H\left({\omega }_j\right)+\left[\left(k-2\right)/k\right]H\left[2{\omega }_j/\left(k-2\right)\right]$ $-\left[d\left(k-2\right)/k\right]H\left[{\omega }_j/\left(k-2\right)\right]+\left(d/k\right)ln\left(k-2\right)+\left({\omega }_{j}d/k\right)·ln\left(k-3\right)-\left({\omega }_{j}d/k\right)ln2$ and $\phi \left(d\right)=\left(d/k\right)lnk+\left(d/k\right)ln\left(k-1\right)$$-\left(2d/k\right)ln2+\left(1-d\right)H\left(2/k\right)$.

Let $f\left({\omega }_j\right)=1/{\left[4\pi \left(2n/k\right){\omega }_j\left(1-{\omega }_j\right)\right]}^{1/2}$, then:

$$\begin{array}{cc}\hfill E\left[Z^2\left(n\right)\right]& \approx E^2\left[Z\left(n\right)\right]\left(\frac{1}{\sqrt{d}}{e}^{-n\phi \left(d\right)}+e^{-n\phi \left(d\right)}{\displaystyle \sum _{j=1}^{2n/k}}f\left({\omega }_j\right)e^{n\psi \left({\omega }_j\right)}\right)\hfill \\ & =E^2\left[Z\left(n\right)\right]\left(\beta e^{-n\phi \left(d\right)}+e^{-n\phi \left(d\right)}{\displaystyle \sum _{j=1}^{2n/k}}f\left({\omega }_j\right)e^{n\psi \left({\omega }_j\right)}\right).\hfill \end{array}$$

where $\beta =1/{\left(d\right)}^{1/2}$.

Convert cumulative sums to integrals as follows:

$$E\left[Z^2\left(n\right)\right]\approx E^2\left[Z\left(n\right)\right]\left(\beta e^{-n\phi \left(d\right)}+e^{-n\phi \left(d\right)}\frac{2n}{k}{\int }_0^{1}f\left(\omega \right)e^{n\psi \left(\omega \right)}d\omega \right).$$

Here,

$$\begin{array}{cc}\hfill \psi \left(\omega \right)& =\frac{2}{k}H\left(\omega \right)+\frac{k-2}{k}H\left(\frac{2\omega }{k-2}\right)-\frac{d\left(k-2\right)}{k}H\left(\frac{\omega }{k-2}\right)+\frac{d}{k}ln\left(k-2\right)+\frac{\omega d}{k}ln\left(k-3\right)-\frac{\omega d}{k}ln2\hfill \\ & =\frac{2}{k}\left[-\omega ln\omega -\left(1-\omega \right)ln\left(1-\omega \right)\right]+\frac{k-2}{k}\left[-\frac{2\omega }{k-2}ln\frac{2\omega }{k-2}-\left(1-\frac{2\omega }{k-2}\right)ln\left(1-\frac{2\omega }{k-2}\right)\right]\hfill \\ & -\frac{d\left(k-2\right)}{k}\left[-\frac{\omega }{k-2}ln\frac{\omega }{k-2}-\left(1-\frac{\omega }{k-2}\right)ln\left(1-\frac{\omega }{k-2}\right)\right]+\frac{\omega d}{k}ln\left(k-3\right)-\frac{\omega d}{k}ln2\hfill \\ & =\frac{d\omega -4\omega }{k}ln\omega -\frac{2\left(1-\omega \right)}{k}ln\left(1-\omega \right)-\frac{2\omega +d\omega }{k}ln2+\frac{k-2-dk+3d}{k}ln\left(k-2\right)\hfill \\ & -\frac{k-2-2\omega }{k}ln\left(k-2-2\omega \right)+\frac{dk-2d-d\omega }{k}ln\left(k-2-\omega \right)+\frac{\omega d}{k}ln\left(k-3\right).\hfill \end{array}$$

Because

$$\begin{array}{cc}\hfill H^{\prime }\left(\omega \right)& ={\left[-\omega ln\omega -\left(1-\omega \right)ln\left(1-\omega \right)\right]}^{\prime }\hfill \\ & =-ln\omega +ln\left(1-\omega \right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill H^{\prime }\left(\frac{2\omega }{k-2}\right)& ={\left[-\frac{2\omega }{k-2}ln\frac{2\omega }{k-2}-\left(1-\frac{2\omega }{k-2}\right)ln\left(1-\frac{2\omega }{k-2}\right)\right]}^{\prime }\hfill \\ & =\frac{2}{k-2}ln\frac{k-2-2\omega }{k-2}-\frac{2}{k-2}ln\frac{2\omega }{k-2},\hfill \end{array}$$

$$\begin{array}{cc}\hfill H^{\prime }\left(\frac{\omega }{k-2}\right)& ={\left[-\frac{\omega }{k-2}ln\frac{\omega }{k-2}-\left(1-\frac{\omega }{k-2}\right)ln\left(1-\frac{\omega }{k-2}\right)\right]}^{\prime }\hfill \\ & =\frac{1}{k-2}ln\frac{k-2-\omega }{k-2}-\frac{1}{k-2}ln\frac{\omega }{k-2}.\hfill \end{array}$$

Thus,

$$\begin{array}{cc}\hfill {\psi }^{\prime }\left(\omega \right)& =\frac{2}{k}\left(ln\left(1-\omega \right)-ln\omega \right)+\frac{k-2}{k}\left(\frac{2}{k-2}ln\frac{k-2-2\omega }{k-2}-\frac{2}{k-2}ln\frac{2\omega }{k-2}\right)\hfill \\ & -\frac{d\left(k-2\right)}{k}\left(\frac{1}{k-2}ln\frac{k-2-\omega }{k-2}-\frac{1}{k-2}ln\frac{\omega }{k-2}\right)+\frac{d}{k}ln\left(k-3\right)-\frac{d}{k}ln2\hfill \\ & =\frac{d-4}{k}ln\omega +\frac{2}{k}ln\left(1-\omega \right)+\frac{2}{k}ln\left(k-2-2\omega \right)-\frac{d}{k}ln\left(k-2-\omega \right)+\frac{d}{k}ln\left(k-3\right)-\frac{2+d}{k}ln2.\hfill \end{array}$$

Therefore, ${\psi }^{″}\left(\omega \right)=\left[\left(d-4\right)/k\right]·\left(1/\omega \right)-\left(2/k\right)·\left[1/\left(1-\omega \right)\right]$ $-\left(4/k\right)·\left[1/\left(k-2-2\omega \right)\right]$$+\left(d/k\right)·\left[1/\left(k-2-\omega \right)\right]$.

When $k=6$, $d^{*}=2.1168$ can be obtained from Theorem 4. The image of the function $\psi \left(\omega \right)$ is shown in Figure 2a.

Therefore, it can be proven that when $k\ge 3,d<d^{*}$, ${\psi }^{″}\left(\omega \right)<0$. The function $\psi \left(\omega \right)$ is smooth in the interval $\left(0,1\right)$, with a unique maximum point.

Let ${\omega }_{max}$ be the maximum point of the function $\psi \left(\omega \right)$. From Reference [12], it can be obtained that:

$$\begin{array}{c}\underset{n\to \infty }{lim}{\int }_0^{1}f\left(\omega \right)e^{n\psi \left(\omega \right)}d\omega \approx f\left({\omega }_{max}\right)\sqrt{\frac{2\pi }{n\left|{\psi }^{″}\left({\omega }_{max}\right)\right|}}·e^{n\psi \left({\omega }_{max}\right)}.\hfill \end{array}$$

Finally,

$$\begin{array}{cc}\hfill E\left[Z^2\left(n\right)\right]& \approx E^2\left[Z\left(n\right)\right]\left(\beta e^{-n\phi \left(d\right)}+e^{-n\phi \left(d\right)}\frac{2n}{k}f\left({\omega }_{max}\right)\sqrt{\frac{2\pi }{n\left|{\psi }^{″}\left({\omega }_{max}\right)\right|}}{e}^{n\psi \left({\omega }_{max}\right)}\right)\hfill \\ & =E^2\left[Z\left(n\right)\right]\left(\beta e^{-n\phi \left(d\right)}+f_1\left({\omega }_{max}\right)n^{\frac{1}{2}}{e}^{n\left(\psi \left({\omega }_{max}\right)-\phi \left(d\right)\right)}\right),\hfill \end{array}$$

where $f_1\left({\omega }_{max}\right)=\left(2/k\right)·{\left[2\pi /\left|{\psi }^{″}\left({\omega }_{max}\right)\right|\right]}^{1/2}·f\left({\omega }_{max}\right)$.

Let,

$$\varphi \left(d\right)=\psi \left({\omega }_{max}\right)-\phi \left(d\right).$$

When $k=6$ and $0<{\omega }_{max}<1$, the image of the function $\varphi \left(d\right)$ is shown in Figure 2b.

Therefore, it can be proven that when $k\ge 3,d<d^{*}$, $\varphi \left(d\right)$ is smooth and non-positive in the interval $\left(0,1\right)$, which has a unique maximum point. Thereby,

$$E\left[Z^2\left(n\right)\right]\approx E^2\left[Z\left(n\right)\right]\left(\beta e^{-n\phi \left(d\right)}+f_1\left({\omega }_{max}\right).\frac{\sqrt{n}}{e^{n\left|\psi \left({\omega }_{max}\right)-\phi \left(d\right)\right|}}\right).$$

Thus, when $d<d^{*},n\to \infty$, $E\left[Z^2\left(n\right)\right]=E^2\left[Z\left(n\right)\right]\left(1+o\left(1\right)\right)$.

In conclusion, $\underset{n\to \infty }{Pr}[Z\left(n\right)=0]=0$, that is, $\underset{n\to \infty }{Pr}[Z\left(n\right)>0]=1$. □

In other words, when $d<d^{*}$, the 2-($d,k$)-SAT instance has high probability to be satisfied. When $d>d^{*}$, the high probability of the 2-($d,k$)-SAT instance cannot be satisfied. Thus, Theorem 4 is proven.

4. Numerical Experiment and Analysis

This section mainly designs experiments to verify the rationality of the derivation of Theorem 4. From the above derivation, it is found that the phase transition point $d^{*}$ is a function of the clause length k. Therefore, we selected the 6 total cases where the clause length $k=4$, $k=6$, and $k=7$, and the variables set sizes are $n=10$ and $n=10$ respectively, to verify. The generation model introduced in the article is used to randomly generate ($d,k$)-SAT instances. When $k=4$, $d^{*}=1.6563$. When $k=6$, $d^{*}=2.1168$ and $k=6$, $d^{*}=2.2803$.

Figure 3, Figure 4 and Figure 5 respectively show the phase transition phenomenon of 2-($d,k$)-SAT instances with the clause lengths $k=4$, $k=6$, and $k=7$, and the number of variables $n=10$ and $n=20$. In the figures, the horizontal axis represents the phase transition control parameter d, and the vertical axis represents the probability that 2-($d,k$)-SAT instance can be satisfied. In the experimental design, because the occurrence times of the argument d and the number of clauses m are rounded off, a small error occurred. However, it can be seen that as the scale of the problem increases, this error gradually decreases. From the figures, for a positive integer d, when $d<d^{\prime }$, the problem can be satisfied with a high probability. When $d>d^{\prime }$, the problem cannot be satisfied with a high probability. The experimental value $d^{\prime }$ is basically the same as the theoretical value $d^{*}$.

In the experiment, we used a brute force method. The algorithm exhausts all the assignments, verifies them one by one, and finds all 2-exactly satisfiable formulas. This algorithm is suitable for solving small-scale examples of the problem. When the problem size increases, the algorithm solving time also increases exponentially. However, when the problem size was increased from 10 to 20, the experimental results were closer to the theoretical results. Therefore, as the scale of the problem further increases, the experimental results will become more and more accurate.

5. Conclusions

This article described s-exact satisfiability. For a ($d,k$)-CNF formula F, if F contains only positive or negative literals, there is a satisfying assignment T with a size of $sn/k$, so that F is s-exactly satisfiable. A random regular ($d,k$)-SAT instance generation model was introduced. By constructing the solution space and using the methods of first and second moments, the satisfiable phase transition point $d^{*}$ for the 2-($d,k$)-SAT problem with only positive literals was provided. $d^{*}$ is a function of k ($k\ge 3$). For a positive integer d, if $d<d^{*}$, the problem can be satisfied with high probability. If $d>d^{*}$, the problem cannot be satisfied with high probability. The 2-($d,k$)-SAT problem is a special case of the s-($d,k$)-SAT problem. This study of the phase transition of the problem contributes to understanding and analyzing the phase transition of the s-($d,k$)-SAT problem and similar problems. In further work, the phase transition of the s-($d,k$)-SAT problem in other cases will be provided by using this method or exploring new methods, such as clauses with both positive and negative literals.