計(jì)算理論16難解性

1、2021-12-101/54Chap 9 難解性 可以從下列文件獲得素材：可以從下列文件獲得素材：難解性難解性素材素材.2/54難解性的含義：難解性的含義： 若某一計(jì)算問(wèn)題在理論上是可若某一計(jì)算問(wèn)題在理論上是可解的，但解法需要耗費(fèi)大量的時(shí)解的，但解法需要耗費(fèi)大量的時(shí)間或空間，以至于無(wú)法在實(shí)踐中間或空間，以至于無(wú)法在實(shí)踐中應(yīng)用，則稱該問(wèn)題是難解的。應(yīng)用，則稱該問(wèn)題是難解的。2021-12-103/54難解性的形式難解性的形式難解性可以有多種形式：難解性可以有

2、多種形式：例如例如 ： 1、一個(gè)大部分時(shí)間容易計(jì)算但偶爾、一個(gè)大部分時(shí)間容易計(jì)算但偶爾很難算的問(wèn)題，僅在最壞情況下是難解很難算的問(wèn)題，僅在最壞情況下是難解的；的； 2、在超級(jí)計(jì)算機(jī)上是易算的，但在、在超級(jí)計(jì)算機(jī)上是易算的，但在PC機(jī)上可能需要過(guò)量時(shí)間的問(wèn)題機(jī)上可能需要過(guò)量時(shí)間的問(wèn)題2021-12-104/54本章的目標(biāo)本章的目標(biāo) 證明存在理論上可判定證明存在理論上可判定但實(shí)際中不可判定的問(wèn)題即但實(shí)際中不可判定的問(wèn)題即可判定而難解的問(wèn)題?？膳卸ǘy解的問(wèn)題。2021-12-105/54 總之：難解性問(wèn)題指的是在最壞情總之

3、：難解性問(wèn)題指的是在最壞情況下復(fù)雜性太大，以至于在任何所能想況下復(fù)雜性太大，以至于在任何所能想象建造出來(lái)的計(jì)算機(jī)上所耗費(fèi)的時(shí)間都象建造出來(lái)的計(jì)算機(jī)上所耗費(fèi)的時(shí)間都將超過(guò)宇宙的余生。將超過(guò)宇宙的余生。 例如：例如：SAT問(wèn)題和所有的問(wèn)題和所有的NP完全問(wèn)完全問(wèn)題。題。2021-12-106/549.1 層次定理層次定理 層次定理的含義：定理中的每一個(gè)都能證明時(shí)層次定理的含義：定理中的每一個(gè)都能證明時(shí)間和空間復(fù)雜性類不全相同，它們形成了一個(gè)層次間和空間復(fù)雜性類不全相同，它們形成了一個(gè)層次結(jié)構(gòu)，其中時(shí)空界限較大的類比時(shí)空界限較小的類結(jié)構(gòu)，其中時(shí)空界限較大的類比時(shí)

4、空界限較小的類包含更多的語(yǔ)言。包含更多的語(yǔ)言。 例如：層次定理能形式化的證明：圖靈機(jī)在更例如：層次定理能形式化的證明：圖靈機(jī)在更多的時(shí)間或空間能擴(kuò)大它所能解的問(wèn)題類。也就是多的時(shí)間或空間能擴(kuò)大它所能解的問(wèn)題類。也就是說(shuō)，圖靈機(jī)在時(shí)間說(shuō)，圖靈機(jī)在時(shí)間n3 內(nèi)比內(nèi)比n2內(nèi)能判定更多的語(yǔ)言。內(nèi)能判定更多的語(yǔ)言。2021-12-107/54層次定理的分類層次定理的分類n空間復(fù)雜性層次定理（簡(jiǎn)單）（簡(jiǎn)單）n時(shí)間復(fù)雜性層次定理（復(fù)雜）（復(fù)雜） 2021-12-108/54函數(shù)函數(shù) f:N N,f(n) =logn 稱為空間可稱為空

5、間可構(gòu)造的，如果函數(shù)把構(gòu)造的，如果函數(shù)把1n（n個(gè)個(gè)1的字符串）的字符串） 映射為映射為f(n)的二進(jìn)制表示，并在空間的二進(jìn)制表示，并在空間O(f(n)內(nèi)是可計(jì)算的。內(nèi)是可計(jì)算的。 含義：如果存在某個(gè)圖靈機(jī)含義：如果存在某個(gè)圖靈機(jī)M，在在O(f(n)空間內(nèi)運(yùn)行，并且在輸入空間內(nèi)運(yùn)行，并且在輸入1n后總能后總能停機(jī)，停機(jī)時(shí)停機(jī)，停機(jī)時(shí)f(n)的的二進(jìn)制表示出現(xiàn)在帶子二進(jìn)制表示出現(xiàn)在帶子上，則上，則f是空間可構(gòu)造的是空間可構(gòu)造的定義9.12021-12-109/54 通常出現(xiàn)的不小于通常出現(xiàn)的不小于logn的的函數(shù)都是空函數(shù)都是空間可構(gòu)造的，例如間可構(gòu)造的，例

6、如logn ，nlogn ，n2. . n2是空間可構(gòu)造的，因?yàn)闄C(jī)器以是空間可構(gòu)造的，因?yàn)闄C(jī)器以1 1n為輸為輸入，通過(guò)數(shù)入，通過(guò)數(shù)1 1的數(shù)目得到的數(shù)目得到n的二進(jìn)制形式，的二進(jìn)制形式，采用標(biāo)推的方法將采用標(biāo)推的方法將n自乘，輸出。全部空間自乘，輸出。全部空間消耗是消耗是O( (n) )，當(dāng)然也是，當(dāng)然也是O( (n2) ) 。 例9.22021-12-1010/54定理9.3 空間層次定理 對(duì)任何空間可構(gòu)造函數(shù)對(duì)任何空間可構(gòu)造函數(shù)f:N N，存在語(yǔ)言存在語(yǔ)言A，在空間在空間O（f（n）內(nèi)可判內(nèi)可判定，但不能在空間定，但不能在空間o（f（n） 證明思路證

7、明思路 必須顯示一個(gè)語(yǔ)言必須顯示一個(gè)語(yǔ)言A具有具有兩個(gè)性質(zhì)：第一，兩個(gè)性質(zhì)：第一，A在空間在空間O（f（n）內(nèi)可判定；第二，內(nèi)可判定；第二，A不能在空間不能在空間o（f（n）判定。判定。2021-12-1011/54 推論9.4 空間層次定理 對(duì)任何兩個(gè)函數(shù)對(duì)任何兩個(gè)函數(shù)f1 ， f2：N N,其中其中f1（n）等于等于o（f2（n），）， f2是空間可構(gòu)是空間可構(gòu)造的，有造的，有SPACE（f1（n）真包含于真包含于SPACE（f2（n） 該推論的作用能夠把不同的空間復(fù)雜該推論的作用能夠把不同的空間復(fù)雜性類分開。性類分開。2021-12-10wbfeng

8、12/54 推論9.5 對(duì)任意兩個(gè)實(shí)數(shù)對(duì)任意兩個(gè)實(shí)數(shù)0r1 r2, ,有有SPACE(n r1)真包含于真包含于SPACE(n r2)也可以用空間層次定理來(lái)分離前也可以用空間層次定理來(lái)分離前面碰到的的兩個(gè)空間復(fù)雜性類。面碰到的的兩個(gè)空間復(fù)雜性類。2021-12-1013/54 推論9.6 NLNL真包含于真包含于PSPACEPSPACE證明：薩維奇定理說(shuō)明證明：薩維奇定理說(shuō)明NL不真包含于不真包含于SPACE(2n ),空間層次定理說(shuō)明空間層次定理說(shuō)明SPACE(2n )真包含于真包含于SPACE(n), ,所以推所以推論成立。論

9、成立。 2021-12-1014/54 推論9.7 PSPACEPSPACE真包含于真包含于EXPSPACEEXPSPACE 意義：判定過(guò)程必須消耗多于多項(xiàng)式意義：判定過(guò)程必須消耗多于多項(xiàng)式的空間。的空間。2021-12-1015/54 定義9.8函數(shù)函數(shù) t:N N,t(n) =nlogn 稱為時(shí)間可稱為時(shí)間可構(gòu)造的，如果函數(shù)把構(gòu)造的，如果函數(shù)把1 1n（n個(gè)個(gè)1 1的字符串）的字符串） 映射為映射為t(n)的二進(jìn)制表示，并在時(shí)間的二進(jìn)制表示，并在時(shí)間O(t(n)內(nèi)是可計(jì)算的。內(nèi)是可計(jì)算的。 含義：如果存在某個(gè)圖靈機(jī)

10、含義：如果存在某個(gè)圖靈機(jī)M，在在時(shí)時(shí)間間O(t(n)內(nèi)運(yùn)行，而且在輸入內(nèi)運(yùn)行，而且在輸入1 1n上啟動(dòng)上啟動(dòng)后后總能停機(jī)，停機(jī)時(shí)總能停機(jī)，停機(jī)時(shí)t(n)的二進(jìn)制表示出現(xiàn)的二進(jìn)制表示出現(xiàn)在帶子上，則在帶子上，則t是時(shí)間可構(gòu)造的。是時(shí)間可構(gòu)造的。2021-12-1016/54 通常出現(xiàn)的不小于通常出現(xiàn)的不小于nlogn的的函數(shù)都是時(shí)函數(shù)都是時(shí)間可構(gòu)造的，例如間可構(gòu)造的，例如nlogn ， , ,n2 2以及以及2 2n 。 是時(shí)間可構(gòu)造的，首先設(shè)計(jì)一個(gè)是時(shí)間可構(gòu)造的，首先設(shè)計(jì)一個(gè)TM，以二進(jìn)制計(jì)算以二進(jìn)制計(jì)算l l的個(gè)數(shù)。為此該的個(gè)數(shù)。為此該TM沿著帶子移動(dòng)沿

11、著帶子移動(dòng)一個(gè)二進(jìn)制計(jì)數(shù)器，每到一個(gè)輸入位置就把它加一個(gè)二進(jìn)制計(jì)數(shù)器，每到一個(gè)輸入位置就把它加1，直至輸入的末端。因?yàn)閷?duì)于，直至輸入的末端。因?yàn)閷?duì)于n個(gè)輸入位置的每個(gè)輸入位置的每一個(gè)都需要消耗一個(gè)都需要消耗O(logn)步，所以這部分工作消步，所以這部分工作消耗耗O(nlogn)步。然后，從步。然后，從n的二進(jìn)制表示中計(jì)算的二進(jìn)制表示中計(jì)算出的出的 二進(jìn)制形式。因?yàn)樯婕暗臄?shù)的長(zhǎng)度是二進(jìn)制形式。因?yàn)樯婕暗臄?shù)的長(zhǎng)度是O(logn) ，所以任何合理的計(jì)算方法都將消耗時(shí)，所以任何合理的計(jì)算方法都將消耗時(shí)間間O(nlogn) 。 例9.9n nn nn n2021-12-10wbfengstaff.sh

12、17/54定理9.10 時(shí)間層次定理 對(duì)于任何時(shí)間可構(gòu)造函數(shù)對(duì)于任何時(shí)間可構(gòu)造函數(shù)t:N N，存在語(yǔ)言存在語(yǔ)言A，在時(shí)間在時(shí)間O（t（n）內(nèi)可判定，內(nèi)可判定，但在時(shí)間但在時(shí)間o（t（n）/logt(n)內(nèi)不可判定內(nèi)不可判定 證明思路證明思路 類似類似10.310.3。2021-12-1018/54 推論9.11 對(duì)任何兩個(gè)函數(shù)對(duì)任何兩個(gè)函數(shù)t1 ， t2：其中其中t1（n）等于等于o(t2（n）/logt2 (n)， t2是時(shí)間可是時(shí)間可構(gòu)造的，有構(gòu)造的，有TIME(t1（n）)真包含于真包含于TIME(t2（n）)。 2021-12-10wbf

13、19/54 推論9.12 對(duì)任意兩個(gè)實(shí)數(shù)對(duì)任意兩個(gè)實(shí)數(shù)0r1 r2 , 有有TIME(n r1 )真包含于真包含于SPACE(n r2 )2021-12-1020/54 推論9.13P真包含于真包含于EXPTIME2021-12-1021/54指數(shù)空間完全性指數(shù)空間完全性證明一個(gè)具體的語(yǔ)言事實(shí)難解需要分兩步：證明一個(gè)具體的語(yǔ)言事實(shí)難解需要分兩步： 第一：圖靈機(jī)在第一：圖靈機(jī)在EXPSPACE內(nèi)比在內(nèi)比在PSPACE內(nèi)判定更多的語(yǔ)言；內(nèi)判定更多的語(yǔ)言； 第二：證明有關(guān)廣義正則表達(dá)式的一第二

14、：證明有關(guān)廣義正則表達(dá)式的一個(gè)具體的語(yǔ)言是個(gè)具體的語(yǔ)言是EXPSPACE完全的，即不完全的，即不能在多項(xiàng)式時(shí)間、也不能在多項(xiàng)式空間內(nèi)能在多項(xiàng)式時(shí)間、也不能在多項(xiàng)式空間內(nèi)判定。判定。2021-12-1022/54定義定義9.149.14語(yǔ)言語(yǔ)言B是是EXPSPACE完全的，當(dāng)且僅當(dāng)：完全的，當(dāng)且僅當(dāng)： （1）B EXPSPACE;并且并且 （2）EXPSPACE中的每個(gè)中的每個(gè)A都是多項(xiàng)都是多項(xiàng)式時(shí)間可歸約到式時(shí)間可歸約到B。2021-12-1023/54廣義正則表達(dá)式廣義正則表達(dá)式 正則表達(dá)式是正則表達(dá)式是， 以及字母

15、表中的符以及字母表中的符號(hào)經(jīng)過(guò)有限次正則運(yùn)算（并、連接和星）得號(hào)經(jīng)過(guò)有限次正則運(yùn)算（并、連接和星）得到的表達(dá)式。到的表達(dá)式。 廣義正則表達(dá)式是允許指數(shù)運(yùn)算（廣義正則表達(dá)式是允許指數(shù)運(yùn)算（）的正則表達(dá)式。的正則表達(dá)式。Rk = Rk = R R REQREX =|Q和和R是等價(jià)的廣義是等價(jià)的廣義正則表達(dá)式正則表達(dá)式24/54定理定理9.159.15EQREX 是是EXPSPACE完全的。完全的。 證明思路：在度量判定證明思路：在度量判定 EQREX 的復(fù)雜性的復(fù)雜性時(shí)，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表時(shí)，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表

16、達(dá)式的長(zhǎng)度是它包含的所有符號(hào)的總數(shù)。達(dá)式的長(zhǎng)度是它包含的所有符號(hào)的總數(shù)。2021-12-1025/54.2 相對(duì)化2021-12-1026/541. 研究的主要的內(nèi)容給出有力證據(jù)否定用對(duì)角化法解決給出有力證據(jù)否定用對(duì)角化法解決P與與NP問(wèn)題的可能性問(wèn)題的可能性.2021-12-1027/542. 幾個(gè)基本概念和定義(1)諭示 （可比喻為 一塊 超級(jí)芯片 ， 外星人的智能禮物） P138:語(yǔ)言B的一個(gè)諭示是一個(gè)能夠報(bào)告某個(gè)串是否為B的成員的外部裝置. 一個(gè)諭示是一個(gè)語(yǔ)言A.(2)諭示

17、圖靈機(jī)MA是通常的圖靈機(jī)附加一條諭示帶, 每當(dāng)M在諭示帶上寫下一個(gè)字符串時(shí),就能在一步計(jì)算內(nèi)得知這個(gè)字符串是否屬于A.2021-12-1028/542. 幾個(gè)基本概念和定義(續(xù))(3)PA采用諭示A的多項(xiàng)式時(shí)間諭示圖靈機(jī)可判定的語(yǔ)言類.(4)NPA采用諭示A的非確定多項(xiàng)式時(shí)間諭示圖靈機(jī)可判定的語(yǔ)言類.2021-12-1029/543. 舉例(1)NPP(1)NPPSATSAT 含義含義: :相對(duì)于可滿足性問(wèn)題的多項(xiàng)式時(shí)間計(jì)相對(duì)于可滿足性問(wèn)題的多項(xiàng)式時(shí)間計(jì)算包含了算包含了NPNP問(wèn)題的全部問(wèn)題的全部. .(2)(2)CO

18、CONP PNP PSATSAT(3)(3)極小公式極小公式: :如果一個(gè)公式?jīng)]有更小的公式與如果一個(gè)公式?jīng)]有更小的公式與之等價(jià)之等價(jià), ,則稱它為極小的則稱它為極小的. .2021-12-1030/54NONMIN-FORMULA=NONMIN-FORMULA=| 不是極小布爾公式不是極小布爾公式 NP OR NP? NPSAT(1)等價(jià)問(wèn)題屬于等價(jià)問(wèn)題屬于CONP(2)諭示諭示SAT檢查是否有檢查是否有更小的等價(jià)公式更小的等價(jià)公式.是則接是則接受受.2021-12-1031/544. 對(duì)角化方法的局限(1)對(duì)角化方

19、法的核心:是一臺(tái)圖靈機(jī)對(duì)另一臺(tái)圖靈機(jī)的模擬.(2)結(jié)論:凡是僅用對(duì)角化方法證明的關(guān)于圖靈機(jī)的定理,當(dāng)給兩臺(tái)機(jī)器以相同諭示的時(shí)候,仍然成立.2021-12-1032/54問(wèn)題n 能否用對(duì)角化方法證明P與NP不同,亦即它們相對(duì)于任何諭示都不同? n能否依據(jù)簡(jiǎn)單的模擬證明說(shuō)明P與NP相等,即證明它們對(duì)于任何諭示都是相等的?2021-12-1033/541) 存在諭示A使得PA NPA2) 存在諭示B使得PB = NPB上述定理表明不太可能用對(duì)角化方法和簡(jiǎn)單模擬的證明來(lái)解決P與NP問(wèn)題.2021-12-10wbfengstaf

20、34/54證明思路證明思路(2)只要令B是PSPACE完全問(wèn)題如TQBF即可. NPTQBFNPSPACE PSPACE PTQBF因?yàn)榭梢园逊谴_定型多項(xiàng)式時(shí)間諭示機(jī)器轉(zhuǎn)變?yōu)榉谴_定型多項(xiàng)式空間機(jī)器.薩維奇定理因?yàn)門QBF是PSAPCE完全的.2021-12-1035/54 構(gòu)造諭示A.設(shè)計(jì)A使得NPA中的某個(gè)語(yǔ)言LA可以證明需要蠻力搜索,因而LA不可能屬于PA.因此可以得出PANPA的結(jié)論. LA=|x A |x| = | NPA PA2021-12-1036/54關(guān) 鍵n構(gòu)造諭示A: 經(jīng)過(guò)所有構(gòu)造步

21、驟以后狀態(tài)沒(méi)有確定下來(lái)的字符串聲明為不在A中.亦即沒(méi)有多項(xiàng)式時(shí)間諭示機(jī)器能夠以諭示A判定LA.2021-12-1037/549.3 電路復(fù)雜性電路復(fù)雜性2021-12-1038/54布爾電路布爾電路n定義.20 n布爾電路是由導(dǎo)線連接的門和輸入的集合。n門的三種形式：與、或、非門n布爾函數(shù)：AND、OR、NOTn門：布爾函數(shù)處理器輸入輸出2021-12-1039/54布爾電路示例布爾電路示例x1輸出門x2x3輸入變量0 x1輸出1x20 x3輸入100111用函數(shù)描述布爾電路的輸入

22、/輸出：Fc:0,1n-0,1Fc(a1,an)=40/54例例9.21 奇偶函數(shù)奇偶函數(shù)parityn:0,1n-0,1輸出輸出1，當(dāng)且僅當(dāng)輸入變，當(dāng)且僅當(dāng)輸入變量中有奇數(shù)個(gè)量中有奇數(shù)個(gè)1x1x2x3x4實(shí)現(xiàn)例10.21 布爾電路2021-12-1041/54電路族電路族n定義9.22 n一個(gè)電路族C是電路的一個(gè)無(wú)窮列表（C0， C1， C2，), 其中Cn有n個(gè)輸入變量。n稱C在0，1上判定語(yǔ)言A，如果對(duì)于每個(gè)字符串w，wA 當(dāng)且僅當(dāng)Cn(w)=1,其中n是w的長(zhǎng)度。n電路的規(guī)模-所包含門的數(shù)

23、目n規(guī)模復(fù)雜度：一個(gè)電路族（C0， C1， C2，)的規(guī)模復(fù)雜度是一個(gè)函數(shù)f:N-N, 其中f(n)是Cn的規(guī)模n深度及復(fù)雜度：電路的深度是從輸入變量到輸出門的最長(zhǎng)路徑的長(zhǎng)度。n規(guī)模極小、深度極小2021-12-1042/54電路復(fù)雜度電路復(fù)雜度n定義9.23 n語(yǔ)言的電路規(guī)模復(fù)雜度是該語(yǔ)言的極小電路族的規(guī)模復(fù)雜度。n語(yǔ)言的電路深度復(fù)雜度是該語(yǔ)言的極小電路族的深度復(fù)雜度。2021-12-1043/54定理定理9.25 cp212n定理10.25設(shè)t:N-N是一個(gè)函數(shù)，t(n) n。若 ，則A的電路復(fù)雜度為 。n時(shí)間復(fù)雜

24、度小的語(yǔ)言，電路復(fù)雜度也小)( ntTimeA)(2ntO2021-12-1044/54證明思路證明思路nM是在時(shí)間t(n)內(nèi)判定A的TM。對(duì)每個(gè)n，構(gòu)造電路Cn模擬M在長(zhǎng)為n的輸入上的運(yùn)算。nCn的門分成行，每一行對(duì)應(yīng)M進(jìn)行運(yùn)算的一個(gè)格局。每一行用導(dǎo)線連到上一行，指示從上一行的格局能夠計(jì)算得到自己的格局。n修改M使得輸入編碼為0，1。nM在進(jìn)入接收狀態(tài)之前，把讀寫頭移到最左單元，寫下空格符號(hào)。這樣就可以指定電路的最后一行的一個(gè)門為輸出門。2021-12-1045/54證明證明M在輸入w上的畫面定義起始格局第二個(gè)格局第

25、t(n)個(gè)格局Cell1,1Cellt(n),1（接受位置） 狀態(tài)和讀寫頭下的符號(hào)表示為一個(gè)單一的復(fù)合字符。 通過(guò)察看cellt(n),1，就能確定M是否已經(jīng)接受。 每一單元的內(nèi)容都由上一行的某些單元來(lái)決定。 celli-1,j-1,celli-1,j,celli-1,j+1-celli,46/54 構(gòu)造電路Cn對(duì)應(yīng)畫面的每一個(gè)單元有多個(gè)門，添加燈表示某些門的輸出。對(duì)于畫面的每個(gè)單元有k盞燈(k是U(XQ)中元素的數(shù)目)?？偣瞜t(n)2盞燈。燈表示為：一個(gè)單元只能有一盞燈開著，如果lighti,j,s開著，celli,j就包含符號(hào)s

26、。通過(guò)考察轉(zhuǎn)移函數(shù)，可以確定影響celli,j的三個(gè)單元的哪些賦值會(huì)使celli,j包含s。)(),(,1 ,Q47/5401010101v一盞燈的電路2021-12-1048/54特殊處理1 畫面左邊界和右邊界的單元,只有上一行的兩個(gè)單元可能影響它的內(nèi)容，修改電路，模擬這種情況。2 第一行的單元對(duì)應(yīng)起始格局，它們的燈用導(dǎo)線連到輸入變量。這些單元的值是由輸入字符串w決定的。Light1,1,q01-w1 light1,1, q00- -w1Light1,2,1-w2 lig

27、ht1,2,0- -w2 light1,n,1-wn light1,n,0- -wn第一行中剩余單元對(duì)應(yīng)帶子上初始值為空的位置的燈亮。3指定輸出門為與lightt(n),1,qaccept相關(guān)聯(lián)的門。2021-12-1049/54定理定理9.26 cp215n布爾電路是可滿足的，如果輸入的某一賦值使電路布爾電路是可滿足的，如果輸入的某一賦值使電路輸出輸出1。n電路可滿足性問(wèn)題電路可滿足性問(wèn)題CIRCUIT-SAT=|C是可是可滿足的布爾電路滿足的布爾電路定理定理10.26 CIRCUIT-SAT是是NP完全的。完全的。1 證明證明CIRCUIT-SAT屬于屬于NP這是顯然的，因?yàn)榉谴_定型多項(xiàng)式時(shí)間圖靈機(jī)很容這是顯然的，因?yàn)榉谴_定型多項(xiàng)式時(shí)間圖靈機(jī)很容易驗(yàn)證電路是否是可滿足的。易驗(yàn)證電路是否是可滿足的。 2021-12-1050/54