随笔-147  评论-223  文章-30  trackbacks-0
经典的复杂性关系 
 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 春秋十二月 阅读(95) 评论(0)  编辑 收藏 引用 所属分类: Compute Theory

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理