比浏览器更快的访问！
12 关系: 健全性，完备性，形式语言，图灵机，BPP，BQP (複雜度)，計算複雜性理論，量子位，量子计算机，零知识证明，PSPACE，數獨。
健全性
#重定向 可靠性定理.
新！!: 交互式证明系统和健全性 · 查看更多 »
完备性
在数学及其相关领域中，一个对象具有完备性，即它不需要添加任何其他元素，这个对象也可称为完备的或完全的。更精确地，可以从多个不同的角度来描述这个定义，同时可以引入完备化这个概念。但是在不同的领域中，“完备”也有不同的含义，特别是在某些领域中，“完备化”的过程并不称为“完备化”，另有其他的表述，请参考代数闭域、紧化或哥德尔不完备定理。.
新！!: 交互式证明系统和完备性 · 查看更多 »
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
新！!: 交互式证明系统和形式语言 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: 交互式证明系统和图灵机 · 查看更多 »
BPP
BPP（Bounded-error, Probabilistic, Polynomial time），在計算複雜性理論中的一種決定性問題 BPP 還可以指：.
新！!: 交互式证明系统和BPP · 查看更多 »
BQP (複雜度)
在計算複雜度理論內，有限錯誤量子多項式時間（bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。.
新！!: 交互式证明系统和BQP (複雜度) · 查看更多 »
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: 交互式证明系统和計算複雜性理論 · 查看更多 »
量子位
#重定向 量子位元.
新！!: 交互式证明系统和量子位 · 查看更多 »
量子计算机
量子计算机（quantum computer）是一种使用量子邏輯進行通用計算的設備。不同於电子计算机（或稱傳統電腦），量子計算用來存儲數據的對象是量子比特，它使用量子演算法來進行數據操作。马约拉纳费米子反粒子就是自己本身的属性，或许是令量子计算机的制造变成现实的一个关键。.
新！!: 交互式证明系统和量子计算机 · 查看更多 »
零知识证明
#重定向 交互式证明系统#.E9.9B.B6.E7.9F.A5.E8.AF.86.E8.AF.81.E6.98.8E.EF.BC.88Zero-knowledge_proofs.EF.BC.89.
新！!: 交互式证明系统和零知识证明 · 查看更多 »
PSPACE
PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.
新！!: 交互式证明系统和PSPACE · 查看更多 »
數獨
數獨 （）是一種邏輯性的數字填充遊戲，玩家須以數字填進每一格，而每行、每列和每個宮（即3x3的大格）有齊1至9所有數字。遊戲設計者會提供一部分的數字，使謎題只有一個答案。 一個已解答的數獨其實是一種多了宮的限制的拉丁方陣，因為同一個數字不可能在同一行、列或宮中出現多於一次-->。 这种游戏只需要逻辑思维能力，与数字运算无关。虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独是锻炼脑筋的好方法。 因为数独上的数字没有运算价值，仅仅代表相互区分的不同个体，因此可以使用其他的符号比如拉丁字母、罗马字母甚至是不同形状的图案代替。 數獨遊戲由日本遊戲公司 Nikoli 於 1986年 發明，意思為「獨身最適數字」。 2005年，數獨遊戲發揚到全世界。.
新！!: 交互式证明系统和數獨 · 查看更多 »
