# Scale-Free Random SAT Instances
## 4 Industrial SAT Instances  
In the previous section, we introduced scale-free random SAT instances. We want this model to generate formulas as close as possible to industrial ones. Therefore, we want to compute the value of \(\beta\) that best fits industrial instances. For this purpose, we have studied the 100 benchmarks (all industrial) used in the SAT Race 2008. All together, they contain \(n=25\),\(693\),\(792\) variables, with a total of \(\sum_{i=1}^{n}K_{i}=349\),\(760\),\(681\) occurrences. Therefore, the average number of occurrences per variable is \(E[K_{i}]=\sum_{i=1}^{n}K_{i}/n=13.6\). If we used the classical (uniform) random model to generate instances with this average number of occurrences, most of the variables would have a number of occurrences very close to \(13.6\). However, in the analyzed industrial instances, close to \(90\%\) of the variables have less than this number of occurrences, and more than \(60\%\) have \(6\) or fewer occurrences. The big value of the average is produced by a small fraction of the variables that have a huge number of occurrences. This indicates that the number of occurrences could be better modeled with a power-law distribution. This was already suggested by [PERSON] et al. [34].  
In order to check if those industrial instances (all together) are scale-free SAT formulas, and estimate the value of \(\beta\), we compute the number of occurrences of each variable of each industrial instance. Then, we rename the indexes of such variables such that \(K_{i}\geq K_{i+1}\)for \(i=1,\ldots,n-1\). Now, before comparing \(K_{i}\) with \(i^{-\beta}/\sum_{j=1}^{n}j^{-\beta}\), we renormalize both functions such that both are defined in \([0,\,1]\) and its integral in this range is \(1\). Hence, we define for the empirical \(K_{i}\), the _empirical_ function \(\phi^{ind}\) as  
\[\phi^{ind}(x)=_{def}\frac{n}{\sum_{j=1}^{n}K_{j}}\,K_{\lfloor n\,x\rfloor} \tag{7}\]  
and, for the theoretical function \(P(i)\), the _theoretical_ function \(\phi(x;\beta,n)\) as  
\[\phi(x;\beta,n)=\frac{n}{\sum_{j=1}^{n}j^{-\beta}}\,\lfloor n\,x\rfloor^{- \beta}\approx\frac{n}{\zeta(\beta)+\frac{1}{1-\beta}n^{1-\beta}}(n\,x)^{- \beta}=\frac{1-\beta}{\frac{(1-\beta)\zeta(\beta)}{n^{1-\beta}}+1}x^{-\beta}\]  
when \(\beta<1\), we obtain  
\[\phi(x;\beta)=\lim_{n\to\infty}\phi(x;\beta,n)=(1-\beta)x^{-\beta} \tag{8}\]  
In Figure 1, we represent both functions with normal axes and with double-logarithmic axes. Notice that in double logarithmic-axes, the slope of \(\phi^{ind}(x)\) allows us to estimate the value of \(\beta=0.82\).  
Theorem 1 allows us to ensure that the distribution of frequencies on the number of occurrences of variables follows a power-law distribution, with exponent \(\delta=1/0.82+1=2.22\).  
Finally, we have generated a scale-free random 3-SAT formula with \(n=10^{7}\) variables, \(m=2.5\times 10^{7}\) clauses and \(\beta=0.82\). In Figure 2, we show the frequencies of occurrences of variables of this formula and compared it with those obtained for the SAT Race 2008, and the line with slope \(\alpha=1/0.82+1=2.22\).  
Figure 1: Estimated industrial function \(\phi^{ind}(x)\) (in red) and power-law function \(\phi(x;0.82)=(1-0.82)\,x^{-0.82}\) (in blue), with normal axes (**left**) and double-logarithmic axes (**right**).  
Figure 2: Comparison of the frequencies of variable occurrences obtained for the whole set of instances used in the SAT Race 2008, and for a scale-free random 3-SAT formula generated with  
\(\beta=0.82\), \(n=10^{7}\) and \(m=2.5\times 10^{7}\). In both cases, the \(x\)-axis represents the number of occurrences, and the \(y\)-axis the number of variables with this number of occurrences. Both axes are logarithmic. It also shows the line with slope \(\alpha=1/0.82+1=2.22\), corresponding to the function \(f(x)=C\,x^{-2.22}\) in double-logarithmic axes.