計(jì)算理論教學(xué)資料-全文預(yù)覽
【正文】 PC的，則X在多項(xiàng)式時(shí)間內(nèi)可解iffP=NP.65. SAT多項(xiàng)式時(shí)間歸約到3SAT(3SAT是NPC的)66. 證明語(yǔ)言L是R././.a) Intuitively想想有沒(méi)有半判定（判定）的TM，.(R)。B∈NP222?！?若有A≤rB，A是不可判定問(wèn)題B不可判定 A不遞歸B不遞歸B可判定A可判定 B是遞歸的A是遞歸的59. 若X多項(xiàng)式時(shí)間歸約到Y(jié)，Y多項(xiàng)式時(shí)間可解，則X多項(xiàng)式時(shí)間可解；若X多項(xiàng)式時(shí)間歸約到Y(jié)，X多項(xiàng)式時(shí)間不可解，則Y多項(xiàng)式時(shí)間不可解60. X多項(xiàng)式時(shí)間歸約到Y(jié)，Y多項(xiàng)式時(shí)間歸約到Z，則X多項(xiàng)式時(shí)間歸約到Z61. PRIME（COMPOSITE）多項(xiàng)式時(shí)間歸約到Factor，但是Factor多項(xiàng)式時(shí)間不能歸約到PRIME（COMPOSITE）。55. 非正則語(yǔ)言的*可能是正則語(yǔ)言。45. L是NP完全語(yǔ)言，則P=NP，iffL∈P46. SAT是NPplete，3SAT，最大可滿足性也是NP完全的47. 覆蓋問(wèn)題，Hamilton圈（有向無(wú)向），旅行商問(wèn)題，背包問(wèn)題都是NPplete。τ2是L1L3的多項(xiàng)式歸約。B. 基于verifier的定義：NP問(wèn)題上建立的非確定機(jī)包含兩步：1) 非確定地猜一個(gè)解2) 用一個(gè)確定的算法判定該解是否為可行解判定一個(gè)給定猜測(cè)值是否滿足該問(wèn)題（可滿足性）的算法稱作verifier，一個(gè)問(wèn)題稱作NP問(wèn)題當(dāng)且僅當(dāng)存在一個(gè)多項(xiàng)式時(shí)間的verifier。37. .，iff它是圖靈可枚舉的；語(yǔ)言是遞歸的，iff它是以字典序Turing可枚舉的。，并存在L1到L2的歸約，則L2也非遞歸。G=（V，Σ，R，S）29. 。23. 如果對(duì)于所有w屬于Σ*，M(w) = f(w)，我們說(shuō)M計(jì)算函數(shù)f，若存在TM計(jì)算f，則f稱為遞歸的。(VΣ)V2，則稱G=（V，Σ，R，S）為Chomsky范式16. 有窮自動(dòng)機(jī)總是停機(jī)。2. DFA( K, Σ, s, F, δ )；NFA（K,Σ，s，F(xiàn)，Δ）3. 每臺(tái)NFA都有一臺(tái)等價(jià)的DFA（method:find closure）4. 有窮自動(dòng)機(jī)接受的語(yǔ)言類(lèi)= 正則語(yǔ)言類(lèi)（正則表達(dá)式描述的語(yǔ)言類(lèi)）5. 正則語(yǔ)言在各種運(yùn)算下封閉6. 語(yǔ)言是正則的，iff其等價(jià)語(yǔ)言中有有窮個(gè)等價(jià)類(lèi)。10. 給定M，只要M接受w，M就接受wR NO設(shè)S = {M| M accepts wRwhenever it accept w}。8. 給定TM M, 帶上是否出現(xiàn)過(guò)a（a∈Σ）？NO設(shè)Write_a = {M,w|M有一條在帶上寫(xiě)a的規(guī)則}；AH = {M,w|M accept w}存在從AH（非遞歸）到﹁Finite的遞歸函數(shù)f，f(“M”,“w”)=M’(“T”,”a”) = Simulate M(w).若M接受w，在帶上寫(xiě)a；否則什么也不寫(xiě)。7. 給定TM M，is L(M) finite? NO設(shè)Finite = {L(M) where L(M) isfinite}。6. ①給定TM M，是否存在在M上停機(jī)的串？NO②給定TM M， M是否在所有上停機(jī)的串？NO設(shè)L = {M|M(a) where a∈Σ*} ，H = {M,w|M(w)停機(jī)}。2. 給定圖靈機(jī)在空串上走了481步還沒(méi)停機(jī)。 所以L1L2206。構(gòu)造判定L1L2的非確定圖靈機(jī)M:M=“對(duì)于輸入字符串w :1) 非確定地將分成兩段x,y，使得w=xy。L2206。L2的非確定圖靈機(jī)M:M=“對(duì)于輸入字符串w :1) 在w上運(yùn)行M1，在w上運(yùn)行M2。 證明NP在并和連接運(yùn)算下封閉。 (3)補(bǔ)：對(duì)任意 L1屬于P 類(lèi)，設(shè)有時(shí)間O(na)判定器M1判定它，對(duì)構(gòu)造判定器M:M=“對(duì)于輸入字符串w :(1) 在w上運(yùn)行M1。3) 若都接受，則接受。L2屬于P類(lèi)，即 P在并的運(yùn)算下封閉。2) 若有一個(gè)接受則接受，否則拒絕。(1) 并：對(duì)任意 L1, L2206。確定型CFL在補(bǔ)下封閉。64. 若X是NPC的，則X在多項(xiàng)式時(shí)間內(nèi)可解iffP=NP.65. SAT多項(xiàng)式時(shí)間歸約到3SAT(3SAT是NPC的)66. 證明語(yǔ)言L是R././.a) Intuitively想想有沒(méi)有半判定（判定）的TM，.(R)。B∈NP222?！?若有A≤rB，A是不可判定問(wèn)題B不可判定 A不遞歸B不遞歸B可判定A可判定 B是遞歸的A是遞歸的59. 若X多項(xiàng)式時(shí)間歸約到Y(jié)，Y多項(xiàng)式時(shí)間可解，則X多項(xiàng)式時(shí)間可解；若X多項(xiàng)式時(shí)間歸約到Y(jié)，X多項(xiàng)式時(shí)間不可解，則Y多項(xiàng)式時(shí)間不可解60. X多項(xiàng)式時(shí)間歸約到Y(jié)，Y多項(xiàng)式時(shí)間歸約到Z，則X多項(xiàng)式時(shí)間歸約到Z61. PRIME（COMPOSITE）多項(xiàng)式時(shí)間歸約到Factor，但是Factor多項(xiàng)式時(shí)間不能歸約到PRIME（COMPOSITE）。55. 非正則語(yǔ)言的*可能是正則語(yǔ)言。45. L是NP完全語(yǔ)言，則P=NP，iffL∈P46. SAT是NPplete，3SAT，最大可滿足性也是NP完全的47. 覆蓋問(wèn)題，Hamilton圈（有向無(wú)向），旅行商問(wèn)題，背包問(wèn)題都是NPplete。τ2是L1L3的多項(xiàng)式歸約。B. 基于verifier的定義：NP問(wèn)題上建立的非確定機(jī)包含兩步：1) 非確定地猜一個(gè)解2) 用一個(gè)確定的算法判定該解是否為可行解判定一個(gè)給定猜測(cè)值是否滿足該問(wèn)題（可滿足性）的算法稱作verifier，一個(gè)問(wèn)題稱作NP問(wèn)題當(dāng)且僅當(dāng)存在一個(gè)多項(xiàng)式時(shí)間的verifier。37. .，iff它是圖靈可枚舉的；語(yǔ)言是遞歸的，iff它是以字典序Turing可枚舉的。，并存在L1到L2的歸約，則L2也非遞歸。G=（V，Σ，R，S）29. 。23. 如果對(duì)于所有w屬于Σ*，M(w) = f(w)，我們說(shuō)M計(jì)算函數(shù)f，若存在TM計(jì)算f，則f稱為遞歸的。(VΣ)V2，則稱G=（V，Σ，R，S）為Chomsky范式16. 有窮自動(dòng)機(jī)總是停機(jī)。2. DFA( K, Σ, s, F, δ )；NFA（K,Σ，s，F(xiàn)，Δ）3. 每臺(tái)NFA都有一臺(tái)等價(jià)的DFA（method:find closure）4. 有窮自動(dòng)機(jī)接受的語(yǔ)言類(lèi)= 正則語(yǔ)言類(lèi)（正則表達(dá)式描述的語(yǔ)言類(lèi)）5. 正則語(yǔ)言在各種運(yùn)算下封閉6. 語(yǔ)言是正則的，iff其等價(jià)語(yǔ)言中有有窮個(gè)等價(jià)類(lèi)。非可數(shù)的集合稱作不可數(shù)的。11. PDAM=（K，Σ，Γ，Δ，s，F(xiàn)），Γ為棧符號(hào)12. PDA接受的語(yǔ)言正好是CFL13. 正則語(yǔ)言（xynz）和CFL（uvnxynz）的泵定理14. L={anbn}∈CFL，L={anb
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1