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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

problem）。利用这种地雷布局作为证明证据，就证明了该问题属于NP类。 不过，如果一个扫雷局面已经保证自洽（数字、标记和未知方格之间没有矛盾），那么判断其是否有解的问题目前虽未被证明为NP完全，但已被证明为co-NP完全（英语：co-NP-complete）。在这种情况下，扫雷还表现出类似于k-...

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

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

。最大独立集一定是极大独立集，但反之未必。 给定一张图，寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题，且即便试图以常数倍近似也是NP困难的。因此，计算机科学家普遍相信不存在解决该问题的高效算法，无论是精确求解还是以常数倍近似求解。 对于图 G = ( V , E...

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

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

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

出發點，而構成一個環。要確定圖中是否存在哈密頓路徑或哈密頓環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密頓路徑有時會跟尤拉路徑一起討論，因為哈密頓路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。 哈密頓路徑是一個拜訪過某圖所有頂點的路徑，且每個頂點只會...

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

BPP=Co-BPP。 BPP是否是NP的子集仍舊是一個公開的問題。 另外NP是否是BPP的子集也是個公開的問題; 如果是的話，則NP=RP並且PH ⊆ {\displaystyle \subseteq } BPP([2]) (大多數人認為不會，因為這代表對一些很難的NP-完全 問題...

問題亦被分類為NP困難問題。 只要求當中某幾個未知數為整數的線性規劃問題叫做混合整數規劃（mixed integer programming, MIP）問題。這類問題通常亦被分類為NP困難問題。 存在著幾類IP和MIP的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全單位模約束矩陣，和約束條件的右邊全為整數的一類。...