比浏览器更快的访问！
25 关系: 功能性問題，多項式，多項式時間，复杂性类，对数，交替式图灵机，建議 (複雜度)，图灵机，BPP，BPP (複雜度)，算法，算法导论，素数，线性规划，罗纳德·李维斯特，隨機存取，EXPTIME，非确定型图灵机，L (複雜度)，NP (複雜度)，P/NP问题，PSPACE，RP (複雜度)，決定性問題，最大公因數。
功能性問題
在計算複雜性理論內，功能性問題或者函式問題（function problem）是一種計算問題（:en:computational problem），我們對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這麼單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。 因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而FNP是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。 對所有能在多項式時間內解決的的功能性問題，一定存在一個雷同的決定型問題，可以用多項式時間圖靈歸約將後者歸約為前者的方式，解決這個功能性問題。舉例，旅行推銷員問題的決定型問題版本如下： 給定這個決定性問題的解答，我們則可以解決旅行推銷員問題如下： 這個演算法將旅行推銷員問題的時間複雜度放進FPNP內（可以在多項式時間之內，以決定性圖靈機和一個能解決NP問題的神諭解決的問題），並且事實上是這個複雜度類的完備問題。.
新！!: P (複雜度)和功能性問題 · 查看更多 »
多項式
多项式（Polynomial）是代数学中的基础概念，是由称为未知数的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。多项式是整式的一种。未知数只有一个的多项式称为一元多项式；例如x^2-3x+4就是一个一元多项式。未知数不止一个的多项式称为多元多项式，例如就是一個三元多项式。 可以写成只由一项构成的多项式也称为单项式。如果一项中不含未知数，则称之为常数项。 多项式在数学的很多分支中乃至许多自然科学以及工程学中都有重要作用。.
新！!: P (複雜度)和多項式 · 查看更多 »
多項式時間
多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n).
新！!: P (複雜度)和多項式時間 · 查看更多 »
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: P (複雜度)和复杂性类 · 查看更多 »
对数
在数学中，真数 x（对于底数 ）的对数是 y 的指数 y，使得 。底数 的值一定不能是1或0（在扩展到复数的复对数情况下不能是1的方根），典型的是、 10或2。数x（对于底数β）的对数通常写为 稱作為以β為底x的對數。 当x和β进一步限制为正实数的时候，对数是1个唯一的实数。 例如，因为 我们可以得出 用日常语言说，以3为底81的对数是4。.
新！!: P (複雜度)和对数 · 查看更多 »
交替式图灵机
交替式图灵机（, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。.
新！!: P (複雜度)和交替式图灵机 · 查看更多 »
建議 (複雜度)
在複雜度類裡面, 一個建議字串是一種以原本輸入的長度n來對圖靈機新增加的輸入，並且不是輸入的資料本身。如果存在一個多項式時間圖靈機具有特性如下：對任何自然數n，存在一個建議字串A，長度是f(n)，並且對任何長度是n的輸入x，機器M在給予x和A為輸入的狀態下可以正確判斷x是否在這個問題上正確，我們說這個決定型問題在複雜度類 P/f(n)裡面。 與建議字串有關最常見的複雜度類是P/poly，這個複雜度類包含建議字串的長度f(n)屬於任何n的多項式的語言。P/poly等同於以下這個複雜度類：對任何n，均存在一個n的多項式大小的布林線路，可以正確決定任何長度為n的輸入。這個等式其中一個方向的推論比較明顯：如果，對任何n，均存在一個多項式大小的布林線路A(n) 可以決定這問題，那我們可以用一個字串代表布林線路，然後圖靈機模擬布林線路的運作。如此一來，則對這問題來說，任何輸入長度為n的話，我們就有一個包含建議字串A(n)的圖靈機可以作正確的決定。等式另一個方向的證明則是先使用了Cook-Levin 理論，推論出我們可以用一個多項式時間的布林線路來模擬一個多項式時間的圖靈機。然後我們注意到，模擬一個有建議字串的圖靈機並不比模擬一個普通的圖靈機來得更難，因為我們可以將建議字串整個包含在線路裡面(因為建議字串是n的多項式大小)。這樣的話，這個方向的等式也成立了。 因為這個恆等式的關係，P/poly有時候我們以以能夠被多項式大小布林線路決定的題目來定義，或者是能被多項式大小非均勻布林線路解決的線路。 P/poly包含了P和BPP。它也包含了一些 不可決定的問題，例如說一些不可決定語言的一元版本，包含了停機問題。因此，對任何f(n)，P/poly不包含在DTIME (f(n))或者NTIME (f(n))裡面。 不只有P可以被用來增加建議字串變成新的複雜度類。舉例說來，我們可以將具有長度為f(n)建議字串的非決定多項式時間圖靈機定義為複雜度類NP/f(n)。 如果我們允許2n這麼長的建議字串，那我們就可以把n這個長度的所有可能輸入值跟對應的答案都寫入這個建議字串內。因此，我們知道任何函式在建議字串長度為2n的條件下一定是可以計算的，所以超過指數長度的建議字串是沒有意義的。 相同的，我們可以定義出L/poly為有多項式長度建議字串的決定型對數空間。 Category:複雜度類.
新！!: P (複雜度)和建議 (複雜度) · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: P (複雜度)和图灵机 · 查看更多 »
BPP
BPP（Bounded-error, Probabilistic, Polynomial time），在計算複雜性理論中的一種決定性問題 BPP 還可以指：.
新！!: P (複雜度)和BPP · 查看更多 »
BPP (複雜度)
在計算複雜度理論裡面，BPP是在多項式時間內以概率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。 在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減.
新！!: P (複雜度)和BPP (複雜度) · 查看更多 »
算法
-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.
新！!: P (複雜度)和算法 · 查看更多 »
算法导论
《算法导论》（Introduction to Algorithms）是基础算法方面最权威、最详细的著作之一，在很多国际著名大学被用于算法课的教材。诸多算法方面的论文将其列入参考文献当中。 该书详细的介绍了诸多常见的算法及数据结构，并用严谨的证明来论证其正确性。每个章节均有例题，适合学习者深入理解。第一版刊行于1990年，2009年最新版为第三版。在许多国家常常以作者姓名首个英文字母被称为CLRS（第一版则简称为CLR）。.
新！!: P (複雜度)和算法导论 · 查看更多 »
素数
質--數（Prime number），又称素--数，指在大於1的自然数中，除了1和該数自身外，無法被其他自然数整除的数（也可定義為只有1與該數本身两个正因数的数）。大於1的自然數若不是質數，則稱之為合數。例如，5是個質數，因為其正因數只有1與5。而6則是個合數，因為除了1與6外，2與3也是其正因數。算術基本定理確立了質數於數論裡的核心地位：任何大於1的整數均可被表示成一串唯一質數之乘積。為了確保該定理的唯一性，1被定義為不是質數，因為在因式分解中可以有任意多個1（如3、1×3、1×1×3等都是3的有效因數分解）。 古希臘數學家歐幾里得於公元前300年前後證明有無限多個質數存在（欧几里得定理）。現時人們已發現多種驗證質數的方法。其中試除法比較簡單，但需時較長：設被測試的自然數為n，使用此方法者需逐一測試2與\sqrt之間的整數，確保它們無一能整除n。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的演算法測試其是否為質數（例如277232917-1是直至2017年底為止已知最大的梅森質數）。雖然人們仍未發現可以完全區別質數與合數的公式，但已建構了質數的分佈模式（亦即質數在大數時的統計模式）。19世紀晚期得到證明的質數定理指出：一個任意自然數n為質數的機率反比於其數位（或n的對數）。 許多有關質數的問題依然未解，如哥德巴赫猜想（每個大於2的偶數可表示成兩個素數之和）及孿生質數猜想（存在無窮多對相差2的質數）。這些問題促進了數論各個分支的發展，主要在於數字的解析或代數方面。質數被用於資訊科技裡的幾個程序中，如公鑰加密利用了難以將大數分解成其質因數之類的性質。質數亦在其他數學領域裡形成了各種廣義化的質數概念，主要出現在代數裡，如質元素及質理想。.
新！!: P (複雜度)和素数 · 查看更多 »
线性规划
在數學中，線性規劃（Linear Programming，簡稱LP）特指目標函數和約束條件皆為線性的最優化問題。 線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理，特別是某些特殊情況，例如：網路流、多商品流量等問題，都被認為非常重要。目前已有大量針對線性規劃算法的研究。很多最優化問題算法都可以分解為線性規劃子問題，然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念，建立了最優化理論的核心思維，例如「對偶」、「分解」、「凸集」的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最終提升產值與營收。乔治·丹齐格被認爲是线性规划之父。.
新！!: P (複雜度)和线性规划 · 查看更多 »
罗纳德·李维斯特
罗纳德·林納·李维斯特 （Ronald Linn Rivest，）是一名美国密码学家。他是麻省理工学院电子工程和计算机科学部门 (EECS)计算机科学的一名教授 和麻省理工学院之 (CSAIL)的成员。他与阿迪·萨莫尔和伦纳德·阿德曼共同发明了RSA加密演算法；以及在密码学和计算机科学等领域做出许多杰出贡献而知名。RSA被广泛使用在计算机安全应用上，包括https。2002年，他与阿迪·萨莫尔和伦纳德·阿德曼一起因在公钥密码学RSA加密演算法取得的杰出贡献而获得图灵奖。.
新！!: P (複雜度)和罗纳德·李维斯特 · 查看更多 »
隨機存取
在計算機科學中，隨機存取（有時亦稱直接存取）代表同一時間存取一組序列中的一個隨意元件。反之則稱循序存取，即是需要更多時間去存取一個遠端元件。介分兩者的傳統圖解就似比較一軸古代畫卷（循序︰所有在元件之前的物料必須事先捲開）及一本圖書（隨機︰可以隨時翻至任何一頁）。而更近現代的例子就如比較卡式磁帶（循序︰我們必須快速跳過早前的歌曲才可聆聽後期的歌曲）及一張CD（隨機︰我們可以隨意跳至我們想要之處）。不過，RAM一詞卻被用以作為電腦中的半導體晶片記憶體電路。 於數據結構中，隨機存取暗指可由一堆數字之中，能夠持續存取N值的能力，而且除了數組（及相關結構，例如動態陣列）以外，絕少數據結構能夠作出類似程序。另外，隨機存取對不少算法，如快速排序及二元搜尋而言不可或缺。其他數據結構，如合併排序，則憑隨機存取作出有效率的輸入、刪除抑或搜尋功能。 Category:電腦數據.
新！!: P (複雜度)和隨機存取 · 查看更多 »
EXPTIME
在計算複雜性理論裡面，EXPTIME（有時稱作EXP）這個複雜度類是一些決定型問題的集合，這些問題可以使用圖靈機在O(2p(n))的時間內解決，這裡的p(n)代表的是n的某個多項式。 用DTIME來定義，則是 我們已經知道 另外，根據時間譜系理論（time hierarchy theorem）以及空間譜系理論（space hierarchy theorem）， 所以至少第一條包含關係中，前三個包含關係中的一個，以及後三個包含關係中的一個，必然是完整包含（沒有相等可能），但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果，則，這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說，EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言，在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義，等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE \subseteq EXPTIME的方式，因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 EXPTIME是指數譜系（exponential hierarchy）內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式，但是使用雙指數函數（Double exponential function）的時間限制2^。使用類似方式可以類推出更高的時間上限。.
新！!: P (複雜度)和EXPTIME · 查看更多 »
非确定型图灵机
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合，\Gamma是带字母表，L, R分别表示读写头向左和向右移动；符号2^ 表示集合A的幂集，即 2^A.
新！!: P (複雜度)和非确定型图灵机 · 查看更多 »
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.
新！!: P (複雜度)和L (複雜度) · 查看更多 »
NP (複雜度)
非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.
新！!: P (複雜度)和NP (複雜度) · 查看更多 »
P/NP问题
P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P.
新！!: P (複雜度)和P/NP问题 · 查看更多 »
PSPACE
PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.
新！!: P (複雜度)和PSPACE · 查看更多 »
RP (複雜度)
在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性：.
新！!: P (複雜度)和RP (複雜度) · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（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 (複雜度)和最大公因數 · 查看更多 »
