标签：randomness help Turing BPP 图灵机多项式 polynomial class

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

52 件事：数字 7：随机性如何帮助计算，BPP 类是什么？ 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.
这是一系列博客文章中的最新一篇，旨在解决“每个博士生都应该知道的 52 件事来做密码学”列表：一组问题汇编，让博士生在第一年结束时了解他们应该知道什么。这篇博文重点介绍了复杂度类 BPP。 So far, during this blog series Ryan has introduced us to complexity classes, and in particular to P:
到目前为止，在这个博客系列中，Ryan 向我们介绍了复杂性类，特别是 P：

P is the class of languages decidable in polynomial time by a deterministic Turing machine.
P 是确定性图灵机在多项式时间内可判定的语言类。

Then, Guy introduced us to complexity class NP:
然后，Guy 向我们介绍了复杂度类 NP：

NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.
NP 是一类可由非确定性图灵机在多项式时间内判定的语言。

This week I am going to introduce the complexity class BPP:
本周我将介绍复杂度类 BPP：

BPP is the class of languages that are recognised by a probabilistic polynomial time Turing machine with an error probability of 13.
BPP 是一类由概率多项式时间图灵机识别的语言，错误概率为 13 。

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.
概率图灵机[1]是一种非确定性图灵机，它根据概率分布在每个点的可用转换之间随机选择。这意味着概率图灵机可以有随机结果。在相同的输入上，它可能有不同的运行时间，在一次接受它，在另一种情况下拒绝它。它也永远不会停止。这个图灵机产生了其他复杂度类，如RP、ZPP和我们在这篇文章中讨论的BPP。

A little about the complexity class BPP

关于复杂度类 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 13. Note that this error probability can be chosen to be any value strictly between 0 and 12 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 P is decreasing.
因此，正如我们从定义中看到的那样，类 BPP（有界误差概率多项式时间）包含可由具有误差概率 13 的概率图灵机在多项式时间内求解的决策问题。请注意，这个误差概率可以被严格地选择为任何值， 0 并且 12 由于一个名为放大引理的结果，我不会在这里进一步讨论。类 BPP 包含 P，即确定性图灵机在多项式时间内可解决的问题类，这是因为确定性图灵机是概率图灵机的特例（采用概率为 1 的唯一可能路径）。正如 Guy 的帖子中所谈到的，有一个开放的（千禧年）问题，即 P = NP 是否存在。BPP 也有类似的问题，即 P = BPP？已知存在于 BPP 中但未知存在于 P 中的问题数量正在减少。

An example of a BPP Problem

BPP 问题的示例 One of the most famous problems known to be in BPP but not known to be in P 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 P is polynomial identity testing[3], the problem of determining whether a polynomial is identically equal to the zero polynomial.
已知在BPP中但不知道在P中存在的最著名的问题之一是确定一个数字是否是质数。然而，最近（2002年）发现了一个确定性的多项式时间算法[2]来解决这个问题，这意味着它确实在P中。另一个已知存在于 BPP 中但目前仍未知存在于 P 中的问题是多项式恒等式检验[3]，即确定多项式是否等同于零多项式的问题。 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.
关于复杂性类的主题，仍有许多非常重要的悬而未决的问题。其中一些问题如果得到解答，可能会对塑造密码学和计算机科学的未来产生重大影响。

标签：randomness,help,Turing,BPP,图灵机,多项式,polynomial,class
From： https://www.cnblogs.com/3cH0-Nu1L/p/18104678

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

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

Probabilistic Turing Machine

A little about the complexity class BPP

An example of a BPP Problem

相关文章

赞助商

阅读排行