取定s的嚴格d-正則隨機(3,2s)-SAT問題的可滿足臨界?

王永平,許道云

1(貴州大學 計算機科學與技術(shù)學院,貴州 貴陽 5 50025)

2(貴州財經(jīng)大學 數(shù)統(tǒng)學院,貴州 貴陽 550 025)

Fig.1 Ratio of satisfiable instances when N=180 and s∈{1,2,…,10}圖1 當N=180 而s=1,2,…,10 時的可滿足實例占比

Fig.2 Average time in seconds for solving an instance when N=180 and s∈{1,2,…,10}圖2 當N=180 而s=1,2,…,10 時,求解一個實例的平均時間(s)

取定整數(shù)5

1 SDRRK2S 模型

2 可滿足臨界分析

本節(jié)主要使用文獻[13]的方法研究嚴格d-正則隨機(3,2s)-SAT 問題在s取定時的可滿足臨界.這一過程主要分成兩步:一是通過構(gòu)造特殊隨機實驗得到一個特殊真值指派是一個嚴格d-正則隨機(k,2s)-CNF 公式解的概率的漸近表達式;二是使用一階矩方法得到嚴格d-正則隨機(3,2s)-SAT 問題在s取定時可滿足臨界值的下界.

2.1 相關(guān)準備

設F是一個嚴格d-正則隨機(k,2s)-CNF 公式.如果F的文字全體組成的多重集是L,則由SDRRK2S 模型可知,L可作為該模型Step 2 中的多重集A.由SDRRK2S 模型還可知,該模型可由L生成(2Ns)!個公式.因此,該(2Ns)!個公式中可滿足的公式占比即為F是可滿足的概率.如果F的文字全體組成的多重集是L′,則由SDRRK2S 模型可知,此時F是可滿足的概率與F的文字全體組成的多重集是L時相應的概率相等.因此在本節(jié)中,約定F的文字全體組成的多重集是某個取定的集合.

設F是一個嚴格d-正則隨機(k,2s)-CNF 公式.注意到,F是否可滿足取決于是否存在作為F解的真值指派.因此,可考慮使用真值指派和公式共同描述該公式可滿足的可能性.設l是F的一個文字,σ∈{0,1}N是一個真值指派.如果σ(l)=1,則稱l是公式F的由σ決定的1-文字;否則是公式F的由σ決定的0-文字.在不致混淆的情況下,簡稱l是1-文字或0-文字.設A(F&σ)是1-文字全體組成的多重集,而B(F&σ)是0-文字全體組成的多重集.進一步,設S(F&σ)是SDRRK2S 模型由多重集A(F&σ)∪B(F&σ)生成的公式全體組成的多重集.于是,真值指派σ是公式F解的概率如下:

2.2 可滿足臨界

Table 1 Numerial solutions of the null point d0 when s∈{10,20,…,100}表1 當s=10,20,…,100 時,唯一零點d0 的數(shù)值解

3 模擬實驗

根據(jù)定理3 的條件d

Step 1.設k=3,用SDRRK2S 模型生成100 個實例.

Step 2.使用Zchaff 求解器[12]分別求解這100 個實例.記求解器成功求解的實例總數(shù)是n,并記不可滿足實例總數(shù)是nu.

Step 3.計算nu/n并記之為rs.顯然,rs表示在成功求解實例中不可滿足實例所占比例.

注意到:當s=30 時,總共需要進行4×12=48 次實驗,而且在各次實驗中,三元對(s,N,d)互不相同.為方便討論,記此48 次實驗中的任意一個是E.設F是一個嚴格d-正則隨機(3,2s)-CNF 公式,其中,參數(shù)s,N以及d恰好是實驗E中三元對的各相應值,則實驗E的100 個實例可看作對公式F的100 次模擬.進一步,實驗E的rs可看作對F是不可滿足的概率的模擬.這說明,我們的實驗是合理的.

表2~表4 分別給出了s=20,30,40 時的模擬實驗結(jié)果,其中,11.8310,22.6038,34.3585 分別是s=20,30,40 時d0的數(shù)值解.由表2 可知:當s=20 時,對于任取的d<11.8310 和N∈{165,180,195,210},都有rs=1.注意到,rs可看作對公式是不可滿足的概率的模擬.因此,表2 支持定理3.同理,表3 和表4 也均支持定理3.

Table 2 Va lues of rs when s=20 and d<11.8310表2 當s=20 并且d<11.8310 時的rs 值

Table 3 Va lues of rs when s=30 and d<22.6038表3 當s=30 并且d<22.6038 時的rs 值

Table 4 Va lues of rs when s=40 and d<34.3585表4 當s=40 并且d<34.3585 時的rs 值

此外,同表2~表4 中各個rs均等于1 一樣,當s=50,60 時,模擬實驗結(jié)果也均為rs=1(為節(jié)約篇幅,我們沒有展示這些結(jié)果).因此,s=50,60 時的模擬實驗結(jié)果也均支持定理3.綜上,模擬實驗結(jié)果驗證了理論證明所得下界的正確性.

注意到:在上述模擬實驗中,各個rs均等于1.這說明定理3 所得下界仍然比較粗糙,需要進一步改進.

4 結(jié)論

基于嚴格正則(k,2s)-CNF 公式,我們提出了每個變量正負出現(xiàn)次數(shù)之差的絕對值均為d的嚴格d-正則(k,2s)-CNF 公式.我們使用了新提出的SDRRK2S 模型生成嚴格d-正則隨機(k,2s)-CNF 公式.初步進行的模擬實驗表明:當整數(shù)5

需要說明的是:從模擬實驗結(jié)果看,本文所得下界仍然比較粗糙,需要進一步改進.此外,研究討論該可滿足臨界值的上界以確定SAT-UNSAT 相變點也十分必要.這些工作將為研究參數(shù)d如何影響公式求解難度以及設計隨機難解實例生成算法奠定基礎(chǔ).