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

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

2、個(gè)大部分時(shí)間容易計(jì)算但偶爾、一個(gè)大部分時(shí)間容易計(jì)算但偶爾很難算的問題，僅在最壞情況下是難解很難算的問題，僅在最壞情況下是難解的；的； 2、在超級(jí)計(jì)算機(jī)上是易算的，但在、在超級(jí)計(jì)算機(jī)上是易算的，但在PC機(jī)上可能需要過量時(shí)間的問題機(jī)上可能需要過量時(shí)間的問題2022-1-26SCU CS Computation4本章的目標(biāo)本章的目標(biāo) 證明存在理論上可判定證明存在理論上可判定但實(shí)際中不可判定的問題即但實(shí)際中不可判定的問題即可判定而難解的問題?？膳卸ǘy解的問題。2022-1-26SCU CS Computation5 總之：難解性問題指的是在最壞情總之：難解性問題指的是在最壞情況下復(fù)雜性太大，以至于在

3、任何所能想況下復(fù)雜性太大，以至于在任何所能想象建造出來(lái)的計(jì)算機(jī)上所耗費(fèi)的時(shí)間都象建造出來(lái)的計(jì)算機(jī)上所耗費(fèi)的時(shí)間都將超過宇宙的余生。將超過宇宙的余生。 例如：例如：SAT問題和所有的問題和所有的NP完全問完全問題。題。2022-1-26SCU CS Computation69.1 層次定理層次定理 層次定理的含義：定理中的每一個(gè)都能證明時(shí)層次定理的含義：定理中的每一個(gè)都能證明時(shí)間和空間復(fù)雜性類不全相同，它們形成了一個(gè)層次間和空間復(fù)雜性類不全相同，它們形成了一個(gè)層次結(jié)構(gòu)，其中時(shí)空界限較大的類比時(shí)空界限較小的類結(jié)構(gòu)，其中時(shí)空界限較大的類比時(shí)空界限較小的類包含更多的語(yǔ)言。包含更多的語(yǔ)言。 例如：層次定

4、理能形式化的證明：圖靈機(jī)在更例如：層次定理能形式化的證明：圖靈機(jī)在更多的時(shí)間或空間能擴(kuò)大它所能解的問題類。也就是多的時(shí)間或空間能擴(kuò)大它所能解的問題類。也就是說，圖靈機(jī)在時(shí)間說，圖靈機(jī)在時(shí)間n3 內(nèi)比內(nèi)比n2內(nèi)能判定更多的語(yǔ)言。內(nèi)能判定更多的語(yǔ)言。2022-1-26SCU CS Computation7層次定理的分類層次定理的分類n空間復(fù)雜性層次定理（簡(jiǎn)單）（簡(jiǎn)單）n時(shí)間復(fù)雜性層次定理（復(fù)雜）（復(fù)雜） 2022-1-26SCU CS Computation8函數(shù)函數(shù) f:N N,f(n) =logn 稱為空間可稱為空間可構(gòu)造的，如果函數(shù)把構(gòu)造的，如果函數(shù)把1n（n個(gè)個(gè)1的字符串）的字符串） 映射

5、為映射為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.12022-1-26SCU CS Computation9 通常出現(xiàn)的不小于通常出現(xiàn)的不小于logn的函數(shù)都是空的函數(shù)都是空間可構(gòu)造的，例如間可構(gòu)造的，例如logn ，nlogn ，n2. . n2是空間可構(gòu)造的，因?yàn)闄C(jī)器以是空間可構(gòu)造的，因?yàn)?/p>

6、機(jī)器以1 1n為輸為輸入，通過數(shù)入，通過數(shù)1 1的數(shù)目得到的數(shù)目得到n的二進(jìn)制形式，的二進(jìn)制形式，采用標(biāo)推的方法將采用標(biāo)推的方法將n自乘，輸出。全部空間自乘，輸出。全部空間消耗是消耗是O( (n) )，當(dāng)然也是，當(dāng)然也是O( (n2) ) 。 例9.22022-1-26SCU CS Computation10定理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） 證明思路證明思路 必須顯示一個(gè)語(yǔ)言必須顯示一個(gè)語(yǔ)言A具有具有兩個(gè)性質(zhì)：第一，兩個(gè)性質(zhì)：第一，A在空間在空間O（

7、f（n）內(nèi)可判定；第二，內(nèi)可判定；第二，A不能在空間不能在空間o（f（n）判定。判定。2022-1-26SCU CS Computation11 推論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ù)雜性類分開。性類分開。2022-1-26SCU CS Computation12 推論9.5 對(duì)任意兩個(gè)實(shí)數(shù)對(duì)任意兩個(gè)實(shí)數(shù)0r1 r2, ,有有SPACE(n r1

8、)真包含于真包含于SPACE(n r2)也可以用空間層次定理來(lái)分離前也可以用空間層次定理來(lái)分離前面碰到的的兩個(gè)空間復(fù)雜性類。面碰到的的兩個(gè)空間復(fù)雜性類。2022-1-26SCU CS Computation13 推論9.6 NLNL真包含于真包含于PSPACEPSPACE證明：薩維奇定理說明證明：薩維奇定理說明NL不真包含于不真包含于SPACE(2n ),空間層次定理說明空間層次定理說明SPACE(2n )真包含于真包含于SPACE(n), ,所以推所以推論成立。論成立。 2022-1-26SCU CS Computation14 推論9.7 PSPACEPSPACE真包含于真包含于EXPSP

9、ACEEXPSPACE 意義：判定過程必須消耗多于多項(xiàng)式意義：判定過程必須消耗多于多項(xiàng)式的空間。的空間。2022-1-26SCU CS Computation15 定義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ī)含義：如果存在某個(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

10、)的二進(jìn)制表示出現(xiàn)的二進(jìn)制表示出現(xiàn)在帶子上，則在帶子上，則t是時(shí)間可構(gòu)造的。是時(shí)間可構(gòu)造的。2022-1-26SCU CS Computation16 通常出現(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)沿著帶子移動(dòng)一個(gè)二進(jìn)制計(jì)數(shù)器，每到一個(gè)輸入位置就把它加一個(gè)二進(jìn)制計(jì)數(shù)器，每到一個(gè)輸入位置就把它加1，直至輸入的末端。因?yàn)閷?duì)于，直至輸入的末端。因?yàn)閷?duì)于n個(gè)輸入位置

11、的每個(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 n2022-1-26SCU CS Computation17定理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)可判定，但

12、在時(shí)間但在時(shí)間o（t（n）/logt(n)內(nèi)不可判定內(nèi)不可判定 證明思路證明思路 類似類似10.310.3。2022-1-26SCU CS Computation18 推論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）)。 2022-1-26SCU CS Computation19 推論9.12 對(duì)任意兩個(gè)實(shí)數(shù)對(duì)任意兩個(gè)實(shí)數(shù)0r1 r2 , 有有TIME(n r1 )真包含于真包含于SPACE(n r2 )2022-1-26S

13、CU CS Computation20 推論9.13P真包含于真包含于EXPTIME2022-1-26SCU CS Computation21指數(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á)式的一第二：證明有關(guān)廣義正則表達(dá)式的一個(gè)具體的語(yǔ)言是個(gè)具體的語(yǔ)言是EXPSPACE完全的，即不完全的，即不能在多項(xiàng)式時(shí)間、也不能在多項(xiàng)式空間內(nèi)能在多項(xiàng)式時(shí)間、也不能在多項(xiàng)式空間內(nèi)判定。判定。2022-1-26SCU CS

14、 Computation22定義定義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。2022-1-26SCU CS Computation23廣義正則表達(dá)式廣義正則表達(dá)式 正則表達(dá)式是正則表達(dá)式是， 以及字母表中的符以及字母表中的符號(hào)經(jīng)過有限次正則運(yùn)算（并、連接和星）得號(hào)經(jīng)過有限次正則運(yùn)算（并、連接和星）得到的表達(dá)式。到的表達(dá)式。 廣義正則表達(dá)式是允許指數(shù)運(yùn)算（廣義正則表達(dá)式是允許指數(shù)運(yùn)算（）的正則表達(dá)式。的正則表達(dá)式。Rk = Rk

15、 = R R REQREX =|Q和和R是等價(jià)的廣義是等價(jià)的廣義正則表達(dá)式正則表達(dá)式k2022-1-26SCU CS Computation24定理定理9.159.15EQREX 是是EXPSPACE完全的。完全的。 證明思路：在度量判定證明思路：在度量判定 EQREX 的復(fù)雜性的復(fù)雜性時(shí)，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表時(shí)，假設(shè)所有指數(shù)都寫成二進(jìn)制整數(shù)。表達(dá)式的長(zhǎng)度是它包含的所有符號(hào)的總數(shù)。達(dá)式的長(zhǎng)度是它包含的所有符號(hào)的總數(shù)。2022-1-26SCU CS Computation25.2 相對(duì)化2022-1-26SCU CS Computation261. 研究的主要的內(nèi)容給出有力證據(jù)否定用

16、對(duì)角化法解決給出有力證據(jù)否定用對(duì)角化法解決P與與NP問題的可能性問題的可能性.2022-1-26SCU CS Computation272. 幾個(gè)基本概念和定義(1)諭示 （可比喻為 一塊 超級(jí)芯片 ， 外星人的智能禮物） P138:語(yǔ)言B的一個(gè)諭示是一個(gè)能夠報(bào)告某個(gè)串是否為B的成員的外部裝置. 一個(gè)諭示是一個(gè)語(yǔ)言A.(2)諭示圖靈機(jī)MA是通常的圖靈機(jī)附加一條諭示帶, 每當(dāng)M在諭示帶上寫下一個(gè)字符串時(shí),就能在一步計(jì)算內(nèi)得知這個(gè)字符串是否屬于A.2022-1-26SCU CS Computation282. 幾個(gè)基本概念和定義(續(xù))(3)PA采用諭示A的多項(xiàng)式時(shí)間諭示圖靈機(jī)可判定的語(yǔ)言類.(4)

17、NPA采用諭示A的非確定多項(xiàng)式時(shí)間諭示圖靈機(jī)可判定的語(yǔ)言類.2022-1-26SCU CS Computation293. 舉例(1)NPP(1)NPPSATSAT 含義含義: :相對(duì)于可滿足性問題的多項(xiàng)式時(shí)間計(jì)相對(duì)于可滿足性問題的多項(xiàng)式時(shí)間計(jì)算包含了算包含了NPNP問題的全部問題的全部. .(2)(2)COCONP PNP PSATSAT(3)(3)極小公式極小公式: :如果一個(gè)公式?jīng)]有更小的公式與如果一個(gè)公式?jīng)]有更小的公式與之等價(jià)之等價(jià), ,則稱它為極小的則稱它為極小的. .2022-1-26SCU CS Computation30NONMIN-FORMULA=NONMIN-FORMULA

18、=| 不是極小布爾公式不是極小布爾公式 NP OR NP? NPSAT(1)等價(jià)問題屬于等價(jià)問題屬于CONP(2)諭示諭示SAT檢查是否有檢查是否有更小的等價(jià)公式更小的等價(jià)公式.是則接是則接受受.2022-1-26SCU CS Computation314. 對(duì)角化方法的局限(1)對(duì)角化方法的核心:是一臺(tái)圖靈機(jī)對(duì)另一臺(tái)圖靈機(jī)的模擬.(2)結(jié)論:凡是僅用對(duì)角化方法證明的關(guān)于圖靈機(jī)的定理,當(dāng)給兩臺(tái)機(jī)器以相同諭示的時(shí)候,仍然成立.2022-1-26SCU CS Computation32問題n 能否用對(duì)角化方法證明P與NP不同,亦即它們相對(duì)于任何諭示都不同? n能否依據(jù)簡(jiǎn)單的模擬證明說明P與NP相等

19、,即證明它們對(duì)于任何諭示都是相等的?2022-1-26SCU CS Computation331) 存在諭示A使得PA NPA2) 存在諭示B使得PB = NPB上述定理表明不太可能用對(duì)角化方法和簡(jiǎn)單模擬的證明來(lái)解決P與NP問題.2022-1-26SCU CS Computation34證明思路證明思路(2)只要令B是PSPACE完全問題如TQBF即可. NPTQBFNPSPACE PSPACE PTQBF因?yàn)榭梢园逊谴_定型多項(xiàng)式時(shí)間諭示機(jī)器轉(zhuǎn)變?yōu)榉谴_定型多項(xiàng)式空間機(jī)器.薩維奇定理因?yàn)門QBF是PSAPCE完全的.2022-1-26SCU CS Computation35 構(gòu)造諭示A.設(shè)計(jì)A使

20、得NPA中的某個(gè)語(yǔ)言LA可以證明需要蠻力搜索,因而LA不可能屬于PA.因此可以得出PANPA的結(jié)論. LA=|x A |x| = | NPA PA2022-1-26SCU CS Computation36關(guān) 鍵n構(gòu)造諭示A: 經(jīng)過所有構(gòu)造步驟以后狀態(tài)沒有確定下來(lái)的字符串聲明為不在A中.亦即沒有多項(xiàng)式時(shí)間諭示機(jī)器能夠以諭示A判定LA.2022-1-26SCU CS Computation379.3 電路復(fù)雜性電路復(fù)雜性2022-1-26SCU CS Computation38布爾電路布爾電路n定義.20 n布爾電路是由導(dǎo)線連接的門和輸入的集合。n門的三種形式：與、或、非門n布爾函數(shù)：AND、OR

21、、NOTn門：布爾函數(shù)處理器輸入輸出2022-1-26SCU CS Computation39布爾電路示例布爾電路示例x1輸出門x2x3輸入變量0 x1輸出1x20 x3輸入100111用函數(shù)描述布爾電路的輸入/輸出：Fc:0,1n-0,1Fc(a1,an)=b2022-1-26SCU CS Computation40例例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 布爾電路2022-1-26SCU CS Computation41電路族電路族n定義9.22 n一個(gè)電路族C是電路的

22、一個(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ù)目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ī)模極小、深度極小2022-1-26SCU CS Computation42電路復(fù)雜度電路復(fù)雜度n定義9.23 n語(yǔ)言的電路規(guī)模復(fù)雜度是該語(yǔ)言的極小電路族的規(guī)模復(fù)雜度。n語(yǔ)言的電路深度復(fù)雜度是該語(yǔ)言的極小電路族的深度復(fù)雜度。2022

23、-1-26SCU CS Computation43定理定理9.25 cp212n定理10.25設(shè)t:N-N是一個(gè)函數(shù)，t(n) n。若 ，則A的電路復(fù)雜度為 。n時(shí)間復(fù)雜度小的語(yǔ)言，電路復(fù)雜度也小)( ntTimeA)(2ntO2022-1-26SCU CS Computation44證明思路證明思路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)。這樣

24、就可以指定電路的最后一行的一個(gè)門為輸出門。2022-1-26SCU CS Computation45證明證明M在輸入w上的畫面定義起始格局第二個(gè)格局第t(n)個(gè)格局Cell1,1Cellt(n),1（接受位置） 狀態(tài)和讀寫頭下的符號(hào)表示為一個(gè)單一的復(fù)合字符。 通過察看cellt(n),1，就能確定M是否已經(jīng)接受。 每一單元的內(nèi)容都由上一行的某些單元來(lái)決定。 celli-1,j-1,celli-1,j,celli-1,j+1-celli,j2022-1-26SCU CS Computation46 構(gòu)造電路Cn對(duì)應(yīng)畫面的每一個(gè)單元有多個(gè)門，添加燈表示某些門的輸出。對(duì)于畫面的每個(gè)單元有k盞燈(k是

25、U(XQ)中元素的數(shù)目)?？偣瞜t(n)2盞燈。燈表示為：一個(gè)單元只能有一盞燈開著，如果lighti,j,s開著，celli,j就包含符號(hào)s。通過考察轉(zhuǎn)移函數(shù)，可以確定影響celli,j的三個(gè)單元的哪些賦值會(huì)使celli,j包含s。)(),(,1 ,Qsntjisjilight2022-1-26SCU CS Computation4701010101v一盞燈的電路2022-1-26SCU CS Computation48特殊處理1 畫面左邊界和右邊界的單元,只有上一行的兩個(gè)單元可能影響它的內(nèi)容，修改電路，模擬這種情況。2 第一行的單元對(duì)應(yīng)起始格局，它們的燈用導(dǎo)線連到輸入變量。這些單元的值是由輸

26、入字符串w決定的。Light1,1,q01-w1 light1,1, q00- -w1Light1,2,1-w2 light1,2,0- -w2 light1,n,1-wn light1,n,0- -wn第一行中剩余單元對(duì)應(yīng)帶子上初始值為空的位置的燈亮。3指定輸出門為與lightt(n),1,qaccept相關(guān)聯(lián)的門。2022-1-26SCU CS Computation49定理定理9.26 cp215n布爾電路是可滿足的，如果輸入的某一賦值使電路布爾電路是可滿足的，如果輸入的某一賦值使電路輸出輸出1。n電路可滿足性問題電路可滿足性問題CIRCUIT-SAT=|C是可滿足的布爾電路是可滿足的布爾電路n定理定理10.26 CIRCUIT-SAT是是NP完全的。完全的。n1 證明證明CIRCUIT-SAT屬于屬于NPn這是顯然的，因?yàn)榉谴_定型多項(xiàng)式時(shí)間圖靈機(jī)這是顯然的，因?yàn)榉谴_定型多項(xiàng)式時(shí)間圖靈機(jī)很容易驗(yàn)證電路是否是可滿足的。很容易驗(yàn)證電路是否是可滿足的。 2022-1-26SCU CS Computation502 證明NP中的任何語(yǔ)言A可