這篇是密碼學(xué)52件事中第7篇.我們只要把問(wèn)題集中在BPP復(fù)雜類問(wèn)題.

目前為止,我們已經(jīng)介紹了一些復(fù)雜類:

• P 是一類能在多項(xiàng)式時(shí)間內(nèi)被可確定的圖靈機(jī)判定的問(wèn)題.
• NP是一類能在多項(xiàng)式時(shí)間內(nèi)被非確定的圖靈機(jī)判定的問(wèn)題.
• BPP是一類在多項(xiàng)式時(shí)間內(nèi)被概率圖靈機(jī)解出的問(wèn)題,并且對(duì)所有的輸入,輸出結(jié)果有錯(cuò)誤的概率在1/3之內(nèi).

概率圖靈機(jī)

BPP類復(fù)雜問(wèn)題的一些概念

一個(gè)BPP類問(wèn)題的例子

[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–Zippel_lemma

原文鏈接：http://bristolcrypto.blogspot.com/2014/11/52-things-number-7-how-does-randomness.html
轉(zhuǎn)載鏈接：https://www.cnblogs.com/zhuowangy2k/p/11759556.html

總結(jié)

以上是生活随笔為你收集整理的[密码学基础][每个信息安全博士生应该知道的52件事][Bristol Cryptography][第7篇]随机性如何辅助计算和什么是BPP类问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。