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