多項式時間和整数分解

快捷方式: 差异，相似，杰卡德相似系数，参考。

多項式時間和整数分解之间的区别

多項式時間 vs. 整数分解

多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n). 在數學中，整數分解（integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。例如，給出45這個數，它可以分解成32 ×5。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。.

多項式

多项式（Polynomial）是代数学中的基础概念，是由称为未知数的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。多项式是整式的一种。未知数只有一个的多项式称为一元多项式；例如x^2-3x+4就是一个一元多项式。未知数不止一个的多项式称为多元多项式，例如就是一個三元多项式。 可以写成只由一项构成的多项式也称为单项式。如果一项中不含未知数，则称之为常数项。 多项式在数学的很多分支中乃至许多自然科学以及工程学中都有重要作用。.

多項式和多項式時間 · 多項式和整数分解 · 查看更多 »

复杂性类

在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.

复杂性类和多項式時間 · 复杂性类和整数分解 · 查看更多 »

算法

-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.

多項式時間和算法 · 整数分解和算法 · 查看更多 »

NP (複雜度)

非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.

NP (複雜度)和多項式時間 · NP (複雜度)和整数分解 · 查看更多 »

P (複雜度)

在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.

P (複雜度)和多項式時間 · P (複雜度)和整数分解 · 查看更多 »

決定性問題

在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.

多項式時間和決定性問題 · 整数分解和決定性問題 · 查看更多 »