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

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

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

在计算机科学中，参数复杂性（英語：parameterized complexity，存在其他译法）是計算複雜性理論的一个分支，其侧重使用与输入输出有关的参数去区分并解决各种运算问题。具体来说，其会将问题转化，使得存在一个复杂度包含上述参数的函数。 假设P≠NP，那么就会有很多问题的时间复杂度并非线性...

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

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

在計算複雜度理論中，計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題的計算資源。很多重要的複雜度類，都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵，但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明瞭。...

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

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

在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。 NP這個有名的複雜度類，可以用NTIME來定義如下： NP = ⋃ k ∈ N NTIME ( n k ) {\displaystyle {\mbox{NP}}=\bigcup...

在計算複雜性理論，一個被稱為線性時間或 Ο(n)時間的演算法，表示此演算法解題所需時間與輸入資料的大小成正比，通常以n表示。換句話說，執行時間與輸入資料大小為線性比例。例如將一列數字加總的所需時間，正比於串列的長度。 然而實際情況常有差距，真實的執行時間很可能與預期的比率相差甚大，尤其在n的值很小...

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

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

在計算複雜性理論，布盧姆加速定理（英語：Blum's speedup theorem）為關於可计算函数複雜度的基本定理，最早由曼纽尔·布卢姆在1967年提出。 選定一種編程語言後，每個可計算函數仍由無窮多個程式實現，該些程式可能各有優劣。給定某個可計算函數和複雜度衡量時，算法理論經常尋找計算...

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

在理論計算機科學中，隨機存取儲存程式機（英語：Random-access stored-program machine，縮寫為RASP）是一種抽象機器，屬於寄存器機，可使用於演算法開發與計算複雜性理論中。隨機存取儲存程式機類似於隨機存取機，這兩者都是一種圖靈機，等價於通用圖靈機。這兩者主要的區別是...

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

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

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

在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hierarchy)，以EXPTIME開始： EXPTIME = ⋃ k ∈ N DTIME ( 2 n k ) {\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N}...

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

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

在可计算性理论和计算复杂性理论中，计算模型（model of computation）描述了如何根据一组输入值计算函数的输出，包含了负责运算、存储和通讯等结构的具体组织方式。它可以用于测量算法的计算复杂度，总结出算法的性能，而不受特定技术和实现方式的性能差异所误导。 计算模型可分为三大类：顺序模型、函数式模型以及同步模型。...

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

在計算複雜性理論內，一個計算問題（computational problem）對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個「最難的」或者「最代表性的」題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難（hard）的題目。...

Stearns，1936年7月5日—）是一名美国杰出的计算机科学家。他是紐約州立大學奧本尼分校计算机科学的一名教授。1993年，他与尤里斯·哈特马尼斯一起因在計算複雜性理論取得的杰出贡献而获得图灵奖。 A. M. Turing Award. 计算机协会. [2013年12月25日]. （原始内容存档于2021-03-14）...

資料庫理論（Database theory）指資料庫與資料庫管理系統的相關理論與研究。 数据管理方面的理论涵盖其他领域，如查询语言的基础、計算複雜性和查询的表达能力（英语：Expressive power (computer science)）、有限模型理论（英语：Finite model...

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

在哲学中，心智计算理论，又名心靈計算理論（ 英語：Computational theory of mind，CTM ）指的是一系列關於「人类心智是一个訊息处理系统」的观点。該理論認為，认知和意识同為一种计算形式。沃倫·麥卡洛克和沃尔特·皮茨（1943）為最早提出神經活動是計算性的人。他们认为神经計算性可以解释认知...

複雜性是非確定性的，不能準確預測未來。 複雜性理論的湧現顯示一個確定性和（複雜的）隨機性二者之間的領域。這被稱為「混沌的邊緣」。 當分析複雜系統時，對初始條件的敏感性並不像混沌理論那樣重要，誠如 Colander 所言，複雜性研究是在混沌研究的對立面。複雜性...

在計算複雜性理論內，隨機存取圖靈機(random-access Turing machines)是一種變版的圖靈機，用來處理大小較小的複雜度類，特別是使用對數時間的複雜度類，像是DLOGTIME以及對數譜系。 在隨機存取圖靈機上，多了一個特殊的指針磁帶，大小是對數空間，字母是二進位單字(0和1)。...