比浏览器更快的访问！
21 关系: 多項式時間，复杂性类，子集，圖靈歸約，冪集，函数，图灵机，無理數，预序关系，解决问题，計算複雜性理論，自反关系，自然数，L (複雜度)，NP (複雜度)，NP完全，P (複雜度)，PSPACE，SAT，決定性問題，指數時間。
多項式時間
多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n).
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
子集
子集，為某個集合中一部分的集合，故亦稱部分集合。 若A和B为集合，且A的所有元素都是B的元素，则有：.
圖靈歸約
圖靈歸約是可计算性理论中的一種歸約，若問題A可圖靈歸約成問題B，是指若問題B的解答已經知道（Rogers 1967, Soare 1987），就可以解問題A，也可以解釋為若一個演算法可以用來處理問題B，就可以處理問題A。較正式的說法，可被圖靈歸約成問題B的問題是指若存在問題B的預言機，就可以求解的問題集合。圖靈歸約可以用在決定性問題及功能性問題。.
冪集
数学上，给定集合S，其幂集\mathcal(S)（或作2^S）是以S的全部子集为元素的集合。以符号表示即为 在公理集合论（例如ZFC集合论）中，幂集公理假定了任何集合的幂集均存在。 \mathcal(S)的任何子集F称为S上的集族.
函数
函數在數學中為兩集合間的一種對應關係：輸入值集合中的每項元素皆能對應唯一一項輸出值集合中的元素。例如實數x對應到其平方x2的關係就是一個函數，若以3作為此函數的輸入值，所得的輸出值便是9。 為方便起見，一般做法是以符號f,g,h等等來指代一個函數。若函數f以x作為輸入值，則其輸出值一般寫作f(x)，讀作f of x。上述的平方函數關係寫成數學式記為f(x).
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
無理數
無理數是指除有理数以外的实数，當中的「理」字来自于拉丁语的rationalis，意思是「理解」，实际是拉丁文对于logos「说明」的翻译，是指无法用两个整数的比来说明一个无理数。 非有理數之實數，不能寫作兩整數之比。若將它寫成小數形式，小數點之後的數字有無限多個，並且不會循環，即无限不循环小数。常見的無理數有大部分的平方根、π和e（其中後兩者同時為超越數）等。無理數的另一特徵是無限的連分數表達式。 傳說中，无理数最早由畢達哥拉斯學派弟子希伯斯发现。他以幾何方法證明\sqrt無法用整数及分數表示。而畢達哥拉斯深信任意数均可用整数及分数表示，不相信無理數的存在。後來希伯斯触犯学派章程，将无理数透露给外人，因而被扔进海中处死，其罪名竟然等同于“渎神”。另見第一次數學危機。 無理數可以通過有理數的分划的概念進行定義。.
预序关系
序关系（简称预序，又称先序，preorder）、在数学中，是一类接近于偏序关系的二元关系，但仅满足自反性和传递性而不满足反对称性。偏序的大多数理论均可扩展到预序。.
解决问题
解决问题，是一种兼具创造性、操作性的思维方式和智力活动。对问题的发现和澄清，经常是解决问题的第一步。許多在人工智慧、工程、數學、醫學中發展及應用的解决问题技巧也和心理學中研究的心理问题解决技术有關。.
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: 歸約和計算複雜性理論 · 查看更多 »
自反关系
自反关系是在逻辑学和数学中一种特殊的二元关系，这样的二元关系被称为自反的，也被称为具有自反性。自反關係的一個例子是關於實數集合的“等於”關係，因為每個實數都等於它自己。自反關係被認為擁有自反性或被認為具備自反性。对称性、传递性以及自反性是定義等價關係的三個屬性。.
自然数
数学中，自然数指用于计数（如「桌子上有三个苹果」）和定序（如「国内第三大城市」）的数字。用于计数时称之为基数，用于定序时称之为序数。 自然数的定义不一，可以指正整数 (1, 2, 3, 4, \ldots)，亦可以指非负整数 (0, 1, 2, 3, 4, \ldots)。前者多在数论中使用，后者多在集合论和计算机科学中使用，也是 标准中所采用的定义。 数学家一般以\mathbb代表以自然数组成的集合。自然数集是一個可數的，無上界的無窮集合。.
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.
新！!: 歸約和L (複雜度) · 查看更多 »
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是此集合的元素數量。.
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新！!: 歸約和P (複雜度) · 查看更多 »
PSPACE
PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.
SAT
SAT測驗（中国大陆通称“赛达考试”；台灣稱「學術水準測驗考試」；香港和澳门地区则无正式译名），前称学术能力测验（Scholastic Aptitude Test）和学术评估测试（Scholastic Assessment Test），是由美國大學委員會委託美國教育測驗服務社定期舉辦的測驗，和ACT一起并作為美國各大學申請入學的重要參考條件之一。第一次考试于1926年舉辦。 SAT測驗分為SAT推理測驗（SAT Reasoning Test，舊稱SAT I）和SAT學科測驗（SAT Subject Test，舊稱SAT II）。目前的SAT I為2016年版，耗時3小時，費用$50（國際生為$81，不計遲到費）。總成績分值為400-1600分，由四個部分组成（數學、實證式閱讀、寫作、論文寫作所组成。論文寫作變為選考 ，參加SAT或ACT考試是大部份美國大學的錄取要求。一些英国在内的许多其他国家的大学也开始承认这项考试。 在2011年前，SAT一直是全国参加人数最多的大学测验。然而，自2011年起，其竞争对手ACT参与人数超过了SAT；该年1,666,017名考生参加了ACT考试，而参加SAT的考生则有1,664,479名。此后，ACT的考生数量一直凌驾于SAT之上。.
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
指數時間
在計算複雜度理論中，指數時間指的是一個問題求解所需要的計算時間m(n)，依輸入--的大小n而呈指數成長（即輸入--的數量依線性成長，所花的時間將會以指數成長）。 以數學術語來說，便是若存在 k > 1，則此m（n）.
重定向到这里：
可化約 (複雜度)，可變換 (複雜度)，多项式时间图灵归约，归约，化約 (複雜度)，约减，规约，變換 (複雜度)。
