RSS订阅信息安全技术跟踪与研究:技术、平台、会议、论文、产业
你现在的位置:首页 / 技术积累 / 正文

52知识点之7:概率图灵机和BPP复杂类

0 技术积累 | 2015年5月14日
转载申明:本站原创,欢迎转载。但转载时请保留原文地址。
原文地址:http://www.vonwei.com/post/7outof52.html

52 Things: Number 7: How does randomness help in computation, and what is the class BPP?

Posted by Christopher Sherfield

原文博客地址:http://bristolcrypto.blogspot.co.uk/2014/11/52-things-number-7-how-does-randomness.html

 

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This blog post concentrates on the Complexity Class BPP.

 

So far, during this blog series Ryan has introduced us to complexity classes, and in particular to P:

  •  is the class of languages decidable in polynomial time by a deterministic Turing machine.

Then, Guy introduced us to complexity class NP: 

  • NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.

This week I am going to introduce the complexity class BPP:

  • BPP is the class of languages that are recognised by a probabilistic polynomial time Turing machine with an error probability of 1/3.

        

         之前的两个知识点分别介绍了复杂类P问题和NP问题,一个是确定性图灵机DTM多项式时间可判定的,一个是非确定性图灵机NDTM多项式时间可判定的。这里介绍另一个复杂类BPP。在计算复杂度理论里面,BPP是在多项式时间内以概率图灵机解出的问题的集合, 并且对所有的输入,输出结果有错误的概率在1/3之内BPP这个简写代表"Bounded-error"(有限错误)"Probabilistic"(机率的)"Polynomial time"(多项式时间)

 

Probabilistic Turing Machine

         A probabilistic Turing Machine [1] is a type of nondeterministic Turing Machine which randomly chooses between the available transitions at each point according to a probability distribution. What this means is that a probabilistic Turing machine can have stochastic results. On the same input, it could have different run times, accept it on one occasion and reject it on another. It could also never stop. This Turing Machine gives rise to other complexity classes such as RP, ZPP and, the one we're discussing in this post, BPP.

         概率图灵机PTM是一类非确定性图灵机,在每个分支点根据某种概率分布随机选择某种可行的转换。这意味着概率图灵机PTM可能拥有随机的结果(与确定性图灵机不同)。针对相同的输入,其运行时间可能不同,而且这次accept状态,下次可能是reject状态。PTM也可能永不停机。这种图灵机产生了很多其它复杂类,如RPZPPBPP等。

 

A little about the complexity class BPP

         So as we have seen from the definition, the class BPP (Bounded-Error probabilistic polynomial time) contains the decision problems that are solvable in polynomial time by a probabilistic Turing machine with error probability 1/3. Note that this error probability can be chosen to be any value strictly between 0 and 1/2 due to a result named the amplification lemma which I will not discuss further here. The class BPP contains P, the class of problems solvable in polynomial time by a deterministic Turing Machine, this is due to the fact that a deterministic Turing Machine is a special case of the probabilistic Turing Machine (taking the only possible path with probability 1). As talked about in Guy's post, there is an open (Millennium) problem conjecturing as to whether P = NP. There is a similar question with BPP, being P = BPP?  The number of problems known to be in BPP but not known to be in is decreasing.

         BPP包含所有由概率图灵机PTM多项式时间可以解决的问题,并且错误概率是13。其实这个错误概率可以选择为01/2之间的任意值(由amplification lemma引起,这里不分析这个引理)。BPP类包含P,因为一个确定性图灵机DTM是概率图灵机PTM的一个特例(考虑一条可能的路径,其概率为1)。之前讨论PNP类时,一个开放性问题是无法确定两者是否等价。这里也有一个类似的问题,PBPP类是否等价?现在的趋势是,已知属于BPP,但不知属于P的问题数目在减少。

 

An example of a BPP Problem

One of the most famous problems known to be in BPP  but not known to be in was determining whether a number was prime. However, recently (2002) a deterministic polynomial time algorithm was found [2] for this problem meaning that it is indeed in P. Another problem known to be in BPP and currently still not known to be in is polynomial identity testing [3], the problem of determining whether a polynomial is identically equal to the zero polynomial.

         一个非常有名的题目已知是BPP但不确定是否是P,是质数检测,也就是求一个给定的数字是否是质数。不过文献[2]中发现了一个确定性多项式时间算法解决这个问题,因而证实这个问题是在P里面。另一个著名的问题是多项式等同测试(即决定一个多项式是否完全等同于一个零多项式),该问题已知属于BPP,但是目前还不知道是否属于P。说不定不久将来,也可以证明该问题也属于P。当所有属于BPP的问题都被证明属于P后,应该可以确定BPPP等价了,但是你能枚举完所有的BPP问题吗?不管怎样,是否等价还是一个开放性问题。

 

There are still many very important unanswered questions on the topic of Complexity Classes. Some of which, if answered, could have a large impact on shaping the future of Cryptography and Computer Science.

         目前在复杂性类方面,还有很多重要的难题。如果其中一些难题解决,将会对密码学和计算机科学未来发展有深远的影响。这也是为什么搞密码的需要了解这些基本的计算复杂度理论。

 

[1] - http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

[2] - http://en.wikipedia.org/wiki/AKS_primality_test

[3] - http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma


  • ------------------分隔线----------------

  • 如果感兴趣,欢迎关注本站微信号,跟踪最新博文信息,手机微信扫一扫下面的二维码,即可关注!
  • 微月信公众号
  • 推荐您阅读更多有关于“ 52知识点   ”的文章

    请填写你的在线分享代码
    上一篇:漫威电影:复仇者联盟2 预习下一篇:52知识点之8:交互式证明与IP复杂度类

    猜你喜欢

    评论列表:

    发表评论

    必填

    选填

    选填

    必填,不填不让过哦,嘻嘻。

    记住我,下次回复时不用重新输入个人信息

    本站介绍
    最近发表
    本年最热文章
    本月最热文章
    网站分类
    文章归档