NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP完備問題...

藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。 卡普的21個問題列表如下。下列问题加上了缩进排版，以表示出這些問題歸約的方向。例如，精确覆盖问题可以歸約到背包問題（Knapsack），因此背包問題是NP-完全問題。 布爾可滿足性問題...

未解決的計算機科學問題：如果一个问题的解可以快速检验正确性，那么这个问题一定可以快速求解吗？ P/NP问题是理论计算机科学中计算复杂度理论领域至今未解决的问题，是克雷数学研究所七題千禧年大奖难题之一。P/NP问题包括复杂度类P与NP的关系。1971年由史提芬·古克（Stephen A. Cook）和列昂尼德·列文（英语：Leonid...

{X}}} 問題，因此我們可以為所有NP問題建造一個可在多項式時間判定其補性質的非確定型圖靈機，意即NP是反NP的子集。因此NP問題的補集合是一個反NP問題的補集合的子集，意即反NP是NP的子集。由於我們已知NP是反NP的子集，因此表示這兩個集合是一樣的，這證明了沒有反NP完全問題可在NP類之中的性質是對稱的（Symmetrical）。...

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。 NP (複雜度) NP完全 P/NP问题 歸約 Michael R. Garey; David...

polynomial，缩写：NP）是计算理论中最重要的集合之一，它包含P和NP-complete。 P問題是指在多项式时间内，可以找出解的決定性問題(decision problem)，而NP問題則包含可在多项式时间內驗證其解是否正確，但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题,...

在計算複雜度理論內，找一個最小的分團覆蓋（clique cover）是一個圖論的NP完全問題。這問題屬於卡普的二十一個NP-完全問題之一，由卡普在1972年的論文"Reducibility Among Combinatorial Problems"證明為NP完全。 分團覆蓋問題（有時叫做分成分團，partition into...

5}的數字和是0。這個問題是NP完全问题，且或許是最容易描述的NP完全問題。 一個等價的問題是：給一個整數集合和另一個整數s，問是否存在某個非空子集，使得子集中的數字和為s。子集合加总问题可以想成是背包問題的一個特例。 用动态规划的方法，能够以伪多项式时间解决子集合加总问题。我们假定输入序列为： x1...

可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布尔可滿足性問題（Boolean satisfiability problem；SAT ）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多的領域皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。...

problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 哈密顿环问题与哈密顿路径问题之间有着很简单的关系： 给定图 G {\displaystyle G} ,通过加入新顶点 v {\displaystyle v}...

Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。 给定一个有限集合 S 和一些 S 的子集，求问是否可以其中的 k 个子集，他们两两不相交。 形式化的定义：给定全集 U {\displaystyle {\mathcal {U}}} ，和...

图着色问题（英語：Graph Coloring Problem，簡稱GCP），又称着色问题，是最著名的NP-完全问题之一。 给定一个无向图 G = ( V , E ) {\displaystyle G=(V,E)} ，其中 V {\displaystyle V} 为顶点集合， E {\displaystyle...

此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美國國家標準和技術研究院（NIST）的 Alan Goldman 首先將此問題命名为中国邮递员问题。...

一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題...

背包问题（英語：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品...

问题（SAT问题）是NP完全問題。即： 「一個布尔方程式是否存在解」这个问题本身是一个NP問題； 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題。 庫克-李文定理是以史蒂芬·库克和利奥尼德·李文（英语：Leonid Levin）為名。 這定理一個非常重要的推论为：如果SAT问题...

purchaser problem）与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数...

判定兩圖是否同胚是一個NP完全的問題。在與同胚相關的研究中，更常探討的議題是研究某圖的細分是否與另一圖的子圖同構。通常會先假設有2圖，H和G，而大部分文獻的研究著重於H的細分圖是否與G的子圖同構，而若H是一個n頂點的環的話，則這個問題相當於哈密頓迴路問題，因此是一個NP完全的問題...

三维匹配问题（3DM）是六个经典NP完全问题之一，是经典的“婚姻问题”的推广，“婚姻问题”的提法是：有几个未婚男子和几个未婚女子以及一张列出双方都表示愿意结合在一起的一对对男子和女子的表格，问是否能安排几对婚姻使得每个人都与自己愿意接受的配偶结婚并且不出现重婚？ 在三维匹配问题中，可以用集合 W {\displaystyle...

在一个全集X中若干子集的集合为S，精确覆盖是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。 在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题，也是卡普的二十一个NP-完全问题之一。 满足以下条件的集合为一个精确覆盖： S*中任意两个集合没有交集，即X中的元素在S*中出现最多一次...

集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 给定全集 U {\displaystyle {\mathcal {U}}} ，以及一个包含 n {\displaystyle...

在計算複雜度理論中，分團問題（clique problem）是圖論中的一個NP完全（NP-complete）問題。 团（clique）是一個圖中兩兩相鄰的一個頂點集，或是一個完全子圖（complete subgraph），如右圖中的1、2、5三個頂點。 分团问题...

的黑格對角相鄰放置的燈泡不影響燈泡計數。 可以將電路可滿足性問題（英语：Circuit satisfiability problem）多項式時間歸約到點亮謎題。由於電路可滿足性問題已知為NP完全，這可用來證明點亮謎題的可解性問題亦為NP完全。也可考慮僅得某一個特定數字（0、1、2、3、4之一）的黑格...

最大割問題（英語：Maximum Cut）是指，給定一張圖，求一種分割方法，將所有頂點（Vertex）分割成两群，同时使得被切斷的邊（Edge）數量最大。该问题是一个NP完备问题。 此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。 雖然最大割問題是 NP-hard 問題...

一个具有伪多项式时间复杂度的NP完全问题称之为弱NP完全问题（英语：Weak NP-completeness），而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为强NP完全问题（英语：Strong NP-completeness）。...

由于哈密顿路径问题是NP完全的，此规约表明最长路径问题的决定版本也是NP完全的。在该决定问题中，输入是图G和数k；如果G中存在至少一條由k条或更多条边的路径，则输出为“是”，否则为“否”。 如果可以在多项式时间内解决最长路径问题，则可以通过找到最长路径，然后将其长度与数k进行比较来将其用于解决该决定问题...

(複雜度)），如果 P {\displaystyle P} 在 C {\displaystyle C} 中，并且 C {\displaystyle C} 中的任何问题利用该归约都可以化归到 P {\displaystyle P} 。例如，NP完全问题在NP类和多项式时间和多对一归约的意义下是完全的。...

如等邊三角形、正六邊形、正八邊形以及特定的矩形比如黃金矩形和白銀矩形等。 從帶有摺痕的平紙重新摺出原來的形狀這一問題已被Marshall Bern和Barry Hayes證明為NP完全問題。其它技術上的結果在《幾何摺紙算法》一書第二部分有更詳細的介紹。 對一張紙不斷對摺，其損失函數為 L = π t...

S_{2}} 这两个集合中所有数的和相等。尽管分区问题属于NP完全问题，但是依然存在伪多项式时间的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。 分区问题存在一个最佳化問題，该问题是将 S {\displaystyle S}...

在計算複雜度理論內，標示了P-完全的決定型問題對於分析 哪些問題很難有效的平行處理， 哪些問題很難在有限空間內解決掉。 相當的有用。 更正式的說，一個決定型問題是P-完全(一個P裡面的完全問題)：若這問題本身在P裡面，且所有在P內的問題，都可以化約為此問題。 特定的化約方式會產生使用差異而且會影響問題集合的大小。...

对NP和P关系问题，NP完备理论给出了如下的暗示：如果要证明NP=P，一个可能的方向是对NP完备问题给出多项式算法；如果要证明NP≠P，那么必然的一个结果是NP完备问题没有多项式算法。 电路复杂性理论在1990年代以前，被众多研究者认为是解决NP与P关系问题...