比浏览器更快的访问！
9 关系: 反NP，复杂性类，BPP (複雜度)，計算複雜性理論，NP (複雜度)，NP完全，RP (複雜度)，ZPP (複雜度)，歸約。
反NP
在計算複雜度理論上，反NP類是複雜度類的其中一類。.
新！!: 完備 (複雜度)和反NP · 查看更多 »
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: 完備 (複雜度)和复杂性类 · 查看更多 »
BPP (複雜度)
在計算複雜度理論裡面，BPP是在多項式時間內以概率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。 在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減.
新！!: 完備 (複雜度)和BPP (複雜度) · 查看更多 »
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: 完備 (複雜度)和計算複雜性理論 · 查看更多 »
NP (複雜度)
非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.
新！!: 完備 (複雜度)和NP (複雜度) · 查看更多 »
NP完全
NP完全或NP完備（NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NPC問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題，題目為 這個問題的答案非常容易驗證，但目前沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間複雜度是Ο(2n)，n是此集合的元素數量。.
新！!: 完備 (複雜度)和NP完全 · 查看更多 »
RP (複雜度)
在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性：.
新！!: 完備 (複雜度)和RP (複雜度) · 查看更多 »
ZPP (複雜度)
在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點：.
新！!: 完備 (複雜度)和ZPP (複雜度) · 查看更多 »
歸約
在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。.
新！!: 完備 (複雜度)和歸約 · 查看更多 »
