相關詞條
-
機率圖靈機
如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。 testin testin
-
機率自動機論
機率自動機論，自動機論的次級學科，主要研究所處環境或內部具有（有限或無限的）隨機因素的自動機。
機率自動機論 配圖 相關連線 -
《上帝擲骰子嗎》
《上帝擲骰子嗎》 摘要 愛因斯坦：「一個人的價值，應該看他貢獻了什麼，而不是他取得了什麼。」 愛因斯坦說：「我不相信上帝是靠擲骰...
《上帝擲骰子嗎》 序 第一章 黃金時代 第二章 烏雲 第三章 火流星 -
丘奇定理
概念給出分析的第一人，圖靈機概念澄清了形式系統概念的內涵；同時，與波斯特...，最終以通用圖靈機概念刻劃了算法可計算性，即“算法可計算的就是通用圖靈機...，而讚賞圖靈論題的主要原因至少有幾點： (1) 通用圖靈機概念澄清了...
-
離散數學學習指導與習題解答（第3版）
1557.2樣本與事件1557.3有限機率空間1587.3.1有限機率空間的定義1587.3.2等機率空間1587.3.3有限機率空間相關定理1597.4條件機率1607.4.1條件機率定義1607.4.2條件機率...
圖書信息 圖書簡介 圖書前言 圖書目錄 -
互動式證明系統
（verifier）和證明者（prover）組成，兩者都可以看作是某類圖靈機。而它的計算...隨機源的圖靈機。一般來說，對給定的L，我們關注的是互動證明中驗證者V這一...對任意的證明者P，V與P互動之後，輸出“x∈L”的機率很小（可以認為小於...
互動證明 NP （AM）和（MA） 零知識證明 -
計算複雜性理論
定義的簡單圖靈機、遞歸函式等都是計算的模型。但當時都只考慮到理論上的可計算...多帶圖靈機模型、隨機存取機器模型等串列計算模型和向量機器模型等並行計算模型。 資源 資源的確切定義決定於計算的模型。例如,對於多帶的圖靈機...
計算複雜性理論 正文 配圖 相關連線 -
ZPP
V是一個機率圖靈機，如果x在X中，它可能接受x，那么證明是一串硬幣翻轉...，驗證者是一個機率多項式時間圖靈機，當x在X中時接受x的機率很大（大於1...：一個集合X的驗證者V是一個圖靈機，這樣：a.如果x在X中，則存在一個使得V...
交點定義 見證和證明 -
非確定性
單帶圖靈機，由一個有限控制器、一條輸入帶和相應的讀寫頭組成。圖靈機的動作...;讀寫頭向左或向右移一個方格。對於給定的狀態和讀寫頭讀到的符號，圖靈機...-符號對,下一動作都是唯一的，這種機器稱為確定型單帶圖靈機；如果有有窮...
非確定性 簡介 NP＝?P問題 非確定性在學術文獻中的解釋 配圖 -
BPP複雜度
定義一個語言 L在 BPP裡面，若且唯若這語言存在一個機率圖靈機 M...， BPP可以僅以決定性圖靈機定義。一個語言 L是在 BPP裡面若且唯若存在一個多項式 p和一個決定性圖靈機 M，滿足• M對任何輸入均操作多項式時間...
定義 與其他複雜度類別的關係 其他特性
