比浏览器更快的访问！
9 关系: 完備 (複雜度)，二进制，图灵机，稀疏語言，L (複雜度)，P (複雜度)，歸約，決定性問題，最大公因數。
完備 (複雜度)
在計算複雜性理論內，一個計算問題(computational problem)對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個"最難的"或者"最代表性的"題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難(hard)的題目。 更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類 C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p 是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的(在給定的歸約條件之下)。 一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全(C-complete)的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。 第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難(C-hard)這種用詞稱呼包含所有C難(C-hard)的問題，例如說，NP難。 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有"計算上簡單"的解法的話，則所有在"C"這類別裡面的問題都有"簡單"的解法。 一般說來，有遞歸可枚舉(recursive enumeration)的複雜度類都會有已知的完備問題，而並非如此的類別則沒有已知的完備問題。舉例來說，NP，反NP，PLS，PPA 都有已知的完備問題，而RP，ZPP，BPP和TFNP則沒有已知的完備問題(雖然這不代表未來不會發現完備問題)。 有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPPM (BPP加上一個M的諭示) 是沒有完備問題的。.
新！!: P-完全和完備 (複雜度) · 查看更多 »
二进制
在數學和數字電路中，二進制（binary）數是指用二進制記數系統，即以2為基數的記數系統表示的數字。這一系統中，通常用兩個不同的符號0（代表零）和1（代表一）來表示。以2為基數代表系統是二進位制的。數字電子電路中，邏輯門的實現直接應用了二進制，因此現代的計算機和依赖計算機的設備裡都用到二進制。每個數字稱為一個位元（二進制位）或比特（Bit，Binary digit的縮寫）。.
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
稀疏語言
在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含\binomnk個字串, 而這個數字則被 nk給限制住。.
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.
新！!: P-完全和L (複雜度) · 查看更多 »
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新！!: P-完全和P (複雜度) · 查看更多 »
歸約
在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。.
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
新！!: P-完全和決定性問題 · 查看更多 »
最大公因數
数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：.
新！!: P-完全和最大公因數 · 查看更多 »
