经典的复杂性关系
P是多项式时间确定型图灵机可识别的语言类，NP是多项式时间
非确定型图灵机可识别的语言类，NPC表示NP完全问题类，coNP表示NP的补，coNPC表示NPC的补。确定型图灵机是一种从不选择移动的特殊的非确定型图灵机，故自然有P属于NP
coNP、coNPC的定义之集合表述
上面顶部的图有个假设前提是：
coNPC不属于NP，即我们相信NP完全问题的补都不属于NP。但
当P=NP或NP=coNP时，可以发现coNPC属于NP
◆ 为什么coNPC属于coNP？
◆ 为什么NPC 不属于coNP？
◆ 为什么P属于coNP?
◆ 当P=NP时，为什么NP=coNP？
◆ 当NP=coNP时，为什么NPC=coNPC？
前文的关系演变图没考虑多项式空间问题类PS与递归问题类（因为那两个条件不会影响到它们），
PS（NPS）是带多项式空间限制的确定型（非确定型）图灵机可接受的语言类，但不限制运行时间可能需超多项式或指数时间，在外围加上PS与递归语言类后如下
◆ 为什么coNP 属于PS？
用于分析加密
无论对称还是公钥加密，统一设加密运算为E，解密为D。对于正常用户，E和D皆为DTM（确定性图灵机）；对于敌手，若攻击对称加密，则E和D为NTM（非确定性图灵机），攻击公钥则解密为NTM。由于E和D输入为密钥和明文或密文，因此DTM和NTM可采用多道/多带结构。DTM代表P类计算，NTM代表NP类计算，故对于公钥加密安全保障要求
P!=NP，这是一个
必要条件。另根据计算理论定理，必有L(NTM)=L(DTM)，但是它对应的DTM可能要多花费指数时间，这亦说明破解公钥的解密是困难的
零知识复杂性关系
依据Oded Goldreich的《密码学基础》，关系如下
相关原文片段引用如下
BPP是可被概率多项式时间图灵机(即随机化算法)识别的语言类，IP是所有具有交互证明系统的语言构成的类，等于多项式空间语言类即前文经典复杂性关系中的PS，如下图所述
SZK!=CZK是因为计算不可分辨不一定能推出统计不可分辨，
BPP!=PZK之原因可理解为BPP是退化的特殊的完备交互证明系统（证明者什么都不做，仅由验证者概率性地决定是否接受或拒绝）。
当（非均匀）单向函数存在时
CZK=IP，涉及的命题与定理如下
也就是说PS类中的每种语言都具有零知识证明系统，比如NP有如下构造
posted on 2024-02-09 22:19
春秋十二月 阅读(448)
评论(0) 编辑 收藏 引用 所属分类:
Compute Theory