交替式图灵机和機率圖靈機

快捷方式: 差异，相似，杰卡德相似系数，参考。

交替式图灵机和機率圖靈機之间的区别

交替式图灵机 vs. 機率圖靈機

交替式图灵机（, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。. 在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變(transition)。 在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面佈滿了許多隨機位元值的確定型圖靈機。 所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止； 甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。 因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。 同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了 RP，Co-RP，BPP and ZPP。 如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。如果我們同時限制兩者，則有了RLP，Co-RLP，BPLP，和ZPLP。 隨機計算對於定義大多數的交互式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。 例如說，IP這個類別等同 PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。 複雜度理論的其中一個重點問題是：是否隨機性增加了演算法的能力？ 換句話說，是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出 P.

复杂性类

在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.

交替式图灵机和复杂性类 · 复杂性类和機率圖靈機 · 查看更多 »

图灵机

图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

交替式图灵机和图灵机 · 图灵机和機率圖靈機 · 查看更多 »

非确定型图灵机

如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合，\Gamma是带字母表，L, R分别表示读写头向左和向右移动；符号2^ 表示集合A的幂集，即 2^A.

交替式图灵机和非确定型图灵机 · 機率圖靈機和非确定型图灵机 · 查看更多 »

計算複雜性理論

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.

交替式图灵机和計算複雜性理論 · 機率圖靈機和計算複雜性理論 · 查看更多 »

NP (複雜度)

非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.

NP (複雜度)和交替式图灵机 · NP (複雜度)和機率圖靈機 · 查看更多 »

PSPACE

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.

PSPACE和交替式图灵机 · PSPACE和機率圖靈機 · 查看更多 »