經(jīng)典的復(fù)雜性關(guān)系
P是多項式時間確定型圖靈機可識別的語言類，NP是多項式時間
非確定型圖靈機可識別的語言類，NPC表示NP完全問題類，coNP表示NP的補，coNPC表示NPC的補。確定型圖靈機是一種從不選擇移動的特殊的非確定型圖靈機，故自然有P屬于NP
coNP、coNPC的定義之集合表述
上面頂部的圖有個假設(shè)前提是：
coNPC不屬于NP，即我們相信NP完全問題的補都不屬于NP。但
當(dāng)P=NP或NP=coNP時，可以發(fā)現(xiàn)coNPC屬于NP
◆ 為什么coNPC屬于coNP？
◆ 為什么NPC 不屬于coNP？
◆ 為什么P屬于coNP?
◆ 當(dāng)P=NP時，為什么NP=coNP？
◆ 當(dāng)NP=coNP時，為什么NPC=coNPC？
前文的關(guān)系演變圖沒考慮多項式空間問題類PS與遞歸問題類（因為那兩個條件不會影響到它們），
PS（NPS）是帶多項式空間限制的確定型（非確定型）圖靈機可接受的語言類，但不限制運行時間可能需超多項式或指數(shù)時間，在外圍加上PS與遞歸語言類后如下
◆ 為什么coNP 屬于PS？
用于分析加密
無論對稱還是公鑰加密，統(tǒng)一設(shè)加密運算為E，解密為D。對于正常用戶，E和D皆為DTM（確定性圖靈機）；對于敵手，若攻擊對稱加密，則E和D為NTM（非確定性圖靈機），攻擊公鑰則解密為NTM。由于E和D輸入為密鑰和明文或密文，因此DTM和NTM可采用多道/多帶結(jié)構(gòu)。DTM代表P類計算，NTM代表NP類計算，故對于公鑰加密安全保障要求
P!=NP，這是一個
必要條件。另根據(jù)計算理論定理，必有L(NTM)=L(DTM)，但是它對應(yīng)的DTM可能要多花費指數(shù)時間，這亦說明破解公鑰的解密是困難的
零知識復(fù)雜性關(guān)系
依據(jù)Oded Goldreich的《密碼學(xué)基礎(chǔ)》，關(guān)系如下
相關(guān)原文片段引用如下
BPP是可被概率多項式時間圖靈機(即隨機化算法)識別的語言類，IP是所有具有交互證明系統(tǒng)的語言構(gòu)成的類，等于多項式空間語言類即前文經(jīng)典復(fù)雜性關(guān)系中的PS，如下圖所述
SZK!=CZK是因為計算不可分辨不一定能推出統(tǒng)計不可分辨，
BPP!=PZK之原因可理解為BPP是退化的特殊的完備交互證明系統(tǒng)（證明者什么都不做，僅由驗證者概率性地決定是否接受或拒絕）。
當(dāng)（非均勻）單向函數(shù)存在時
CZK=IP，涉及的命題與定理如下
也就是說PS類中的每種語言都具有零知識證明系統(tǒng)，比如NP有如下構(gòu)造
posted on 2024-02-09 22:19
春秋十二月 閱讀(1077)
評論(0) 編輯 收藏 引用 所屬分類:
Compute Theory