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