arithmetic（英语：Presburger arithmetic）、布尔可满足性问题（参见SAT solver）和背包问题。 计算机科学主题 時間複雜度 遊戲複雜度 空间复杂度 计算理论 可计算性理论 計算複雜性理論 Khuller, S. and Vazirani, V. V. 1991. Planar graph coloring...

要用多少时间、要用多少存储（即計算複雜性理論） 這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」 計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於理論計算機科學和應用數學。 為了對計算...

量子计算机（英語：Quantum computer）是一种使用量子力学進行通用計算的設備。但這与电子计算机（或稱傳統電腦）不同，量子計算用來儲存數據的對象是量子位元，它使用量子演算法操作數據。然而，与经典计算机的比特只能处于两个状态之一（0或1）不同，量子比特可以处于这两个基态之间的叠加态，也就是说...

計算及不可計算的可能性更加深入的說明。 計算複雜性理論 - 計算課題上的基本界限(特別是時間及儲存空間)。 量子電腦理論 - 演算法 - 用來解決許多問題的序列及並列的計算程序。 資料結構 - 資料的組織及運作。 編譯理論 - 以自動機理論為基礎設計編譯器的理論。 程式語言 -...

在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（英語：Decision problem）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與...

預膨脹算術（英语：Presburger arithmetic）的決策程序 計算葛洛拿基底（英语：Gröbner basis）（在最差狀況） 實封閉體的量詞消去至少耗費雙重指數時間，而且可以在這樣的時間內完成。 L符號 博弈复杂度 計算複雜性理論 零一律 柯爾莫哥洛夫空間 柯氏复杂性 空间复杂度 Mehlhorn, Kurt; Naher...

根据Elesevier出版社《理論電腦科學雜誌》（Theoretical Computer Science）的解释，理論電腦科學有着数学和抽象的本质，但动机来自实践和日常中的计算问题。它旨在理解计算的本质，并根据这种理解提供更有效率的方法。 精确地限制定义理论计算机科学的范围并非易事；根据计算机协会(ACM)算法与计算理论兴趣组（SIGACT）的表述：...

在可計算性理論與計算複雜性理論中，所謂的歸約是將某個計算問題（英语：computational problem）轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。...

0年，2009年最新版为第三版。在许多国家常常以作者姓名首个英文字母被称为CLRS（第一版则简称为CLR）。 计算机科学主题 计算机程序设计主题 计算理论 可计算性理论 計算複雜性理論 计算机程序设计艺术 Introduction to Algorithms—CiteSeerX citation query...

量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部份。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。...

史蒂芬·亞瑟·库克（英語：Stephen Arthur Cook，1939年12月14日—）是一名美國計算機科學家，計算複雜性理論的重要研究者。 1971年，在他的論文《定理證明程式的複雜性》（The Complexity of Theorem Proving Procedures），他整理了NP完備...

计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算...

六貫棋（英語：Hex）是在六邊形格的棋盤上玩的圖版遊戲，亦是數學遊戲，通常使用10乘10或11乘11的菱形棋盤（約翰·納什則採用14×14的棋盤）。 在計算複雜性理論，六貫棋的複雜性已證明了是PSPACE完全的。(注意不少抽象策略遊戲如國際跳棋、象棋和圍棋都是EXPTIME完全。)...

Kolmogorov，1903年4月25日—1987年10月20日），俄国數學家，主要研究概率論、算法信息論、拓撲學、直觉主义逻辑、紊流、经典力学和計算複雜性理論，最為人所道的是對概率論公理化所作出的貢獻。他曾說：「概率論作為數學學科，可以而且應該從公理開始建設，和幾何、代數的路一樣」。...

在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。 图灵机和邱奇－图灵论题 我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0...

在計算複雜性理論，間隙定理，又稱鮑羅丁－特拉赫堅布羅特間隙定理，為與可计算函数複雜度有關的重要定理。 定理斷言，复杂性类的層階之間，有任意大的可計算間隙。意思是，若給定任意一個可計算函數 g {\displaystyle g} ，表示計算資源增加一次的效果，則必能找到某個資源上限 T ( n ) {\displaystyle...

理論則是對系統的既不可預測而又是決定的行為作明確的描述。 離散數學是指對理論電腦科學最有用處的數學領域之總稱，這包含有可計算理論、計算複雜性理論及資訊理論。可計算理論檢驗電腦的不同理論模型之極限，這包含現知最有力的模型——圖靈機[需要較佳来源]。複雜性理論...

BPP可以指： BPP (複雜度)（Bounded-error, Probabilistic, Polynomial time），在計算複雜性理論中的一種決定性問題 表示色彩深度的單位，指每儲存1像素圖點所需要的位元數（bits per pixel） 黑豹黨（Black Panther Party），美國政黨...

曼纽尔·布卢姆 （英語：Manuel Blum，1938年4月26日—），委内瑞拉计算机科学家，在1995年因在計算複雜性理論的杰出贡献以及在密码学和编程校验上的应用而获得图灵奖。 Manuel Blum在數學譜系計畫的資料。. ACM Turing Award Citation Archive-It的存檔，存档日期2012-07-03...

说，这个论题声称有算法的任何函数都是可计算的。 可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。 计算函数是在自然数上的有限偏函数。每个可计算函数 f {\displaystyle f}...

量子计算优越性（英文：Quantum Advantage），或稱量子霸權（英語：quantum supremacy），是指用量子计算机解決古典電腦难以解决的問題，問題本身未必需要有實際應用。量子计算优越性則是指量子電腦在解決實務問題上能比古典電腦更快而帶來的優勢，從計算複雜性理論...

算术电路是指在计算复杂性理论中，计算多项式的一个计算模型。对于一个给定的域F，一个算术电路计算一个在F[x1,...,xn]中的多项式。它一般被认为是计算多项式最自然的计算模型，并可以看作是存储多项式的数据结构。而证明某些多项式如积和式在算术电路下需要操作步骤的下界问题是计算复杂性理论中的重要的未解决的问题。...

多項式時間（英語：Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間 m ( n ) {\displaystyle m(n)} 不大於問題大小 n {\displaystyle n} 的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說...

主辦的國際數學家大會上頒發一次，以表彰在資訊科學數學方面的傑出貢獻，包括: 電腦科學的所有數學方面，包括計算複雜性理論、编程语言邏輯、算法分析、密码学、计算机视觉、模式识别、資訊處理、和智慧建模。 运算科学和數值分析。 數學最优化和控制理論的計算方面。 計算機代數系統。 獎項於1981年由國際數學家大會執行委員會設立，以紀...

它擁有能對暫存器間接定址的能力。隨機存取機是圖靈機的一種，等價於通用圖靈機。隨機存取機屬於哈佛架構，與電子計算機的特徵近似；如果修改為馮紐曼架構，則成為隨機存取儲存程式機（RASP）。 與圖靈機、計數器機模型相同，隨機存取機器與隨機存取儲存程式機，都常被用於計算複雜性理論之中。 隨機存取儲存程式機...

散時間模型，可應用於電腦科學或電腦工程。在計算理論中，抽象機器經常被當成是一種思想實驗，用來推論可計算性（computability），或是分析演算法的時間複雜度及空间复杂度。 计算机科学主题 计算机程序设计主题 抽象機器 垃圾进，垃圾出 算法导论 计算理论 可计算性理论 計算複雜性理論 高级综合...

在计算机科学和运筹学中，近似算法（英語：Approximation algorithm）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理論...

在计算复杂性理论中，#P（读作sharp P）是一组与NP中的判定性问题相关的计数问题。 Complexity Zoo: Class #P（页面存档备份，存于互联网档案馆）...

电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题的可能的途径之一。电路复杂性研究的对象是非一致性的计算模型电路，并考虑计算一个布尔函数所需的最小的电路的深度（depth）和大小（size）等资源。其中，大小为多项式大小的电路族可以计算...

在计算复杂性理论中，计算资源是一些计算模型在解决计算问题时使用的资源。 最简单的计算资源是计算时间，即解决一个问题所需的步骤数，以及内存空间，即解决问题时需要的存储量，但也有许多更复杂的资源被定义。  [需要引用] 一个计算问题一般[引用]是以其对任何有效输入的行动来定义的。问题的例子可能是 "给定一个整数n，确定n是否是素数"，或者...

5 {\displaystyle 3^{2}\times 5} 。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。 完整的因子列表可以根據因數分解推導出，將冪從零不斷增加直到等於這個數，算出可以整除這個數的所有整數。 例如，因為...