NP完全或NP完备，是计算复杂度理论中，决定性问题的等级之一。NP完备是NP与NP困难问题的交集，是NP中最难的决定性问题，所有NP问题都可以在多项式时间内被归约为NP完备问题。倘若任何NP完备问题得到多项式时间内的解法，则该解法就可应用在所有NP上，亦可证明NP问题等于P问题，然而目前为止并未发现任何能在多项式时间内解决NP完备问题的方法。
1
图论中的经典问题与分别是来确定在一个给定的图上是否存在哈密顿路径和哈密顿环。两个问题皆为NP完全。
数织是一种逻辑游戏，以猜谜的方式绘画二值图像位图。在一个网格中，每一行和列都有一组数，玩家需根据它们来填满或留空格子，最后就可以由此得出一幅图画。例如，“4 8 3”的意思就是指该行或列上有三条独立的线，分别占了4、8和3格，而每条线最少要由一个空格分开。传统上，玩家是以黑色填满格子，和以“×”号标记一定不需要填充的格子。数织是一个NP完全的问题。
可满足性是用来解决给定的真值方程式，是否存在一组变量赋值，使问题为可满足。布尔可满足性问题属于决定性问题，也是第一个被证明属于NP完全的问题。此问题在电脑科学上许多的领域皆相当重要，包括电脑科学基础理论、算法、人工智能、硬件设计等等。
在图论中，是在无向图或有向图中，恰好能将图中所有顶点各拜访一次的路径。与之相近的概念为，即该路径在拜访完图中所有顶点后会回到出发点，而构成一个环。要确定图中是否存在哈密顿路径或哈密顿环的问题称为哈密顿路径问题，这个问题是一个NP完全的问题。哈密顿路径有时会跟尤拉路径一起讨论，因为哈密顿路径要求通过所有顶点而尤拉路径要求通过所有边。
在图论中，是在无向图或有向图中，恰好能将图中所有顶点各拜访一次的路径。与之相近的概念为，即该路径在拜访完图中所有顶点后会回到出发点，而构成一个环。要确定图中是否存在哈密顿路径或哈密顿环的问题称为哈密顿路径问题，这个问题是一个NP完全的问题。哈密顿路径有时会跟尤拉路径一起讨论，因为哈密顿路径要求通过所有顶点而尤拉路径要求通过所有边。
在图论中，是在无向图或有向图中，恰好能将图中所有顶点各拜访一次的路径。与之相近的概念为，即该路径在拜访完图中所有顶点后会回到出发点，而构成一个环。要确定图中是否存在哈密顿路径或哈密顿环的问题称为哈密顿路径问题，这个问题是一个NP完全的问题。哈密顿路径有时会跟尤拉路径一起讨论，因为哈密顿路径要求通过所有顶点而尤拉路径要求通过所有边。
数织是一种逻辑游戏，以猜谜的方式绘画二值图像位图。在一个网格中，每一行和列都有一组数，玩家需根据它们来填满或留空格子，最后就可以由此得出一幅图画。例如，“4 8 3”的意思就是指该行或列上有三条独立的线，分别占了4、8和3格，而每条线最少要由一个空格分开。传统上，玩家是以黑色填满格子，和以“×”号标记一定不需要填充的格子。数织是一个NP完全的问题。
子集和问题，又称子集合加总问题，是计算复杂度理论和密码学中一个很重要的问题。问题可以描述为：给一个整数集合，问是否存在某个非空子集，使得子集内中的数字和为某个特定数值。例：给定集合{−7, −3, −2, 5, 8}，是否存在子集和为0的集合?答案是YES，因为子集{−3, −2, 5}的数字和是0。这个问题是NP完全问题，且或许是最容易描述的NP完全问题。
在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。团是图论中的基本概念之一，用在很多数学问题以及图的构造上。计算机科学中也有对它的研究，尽管在一个图中寻找给定大小的团达到了NP完全的难度，人们还是研究过很多寻找团的算法。
图论中的经典问题与分别是来确定在一个给定的图上是否存在哈密顿路径和哈密顿环。两个问题皆为NP完全。
Mini wiki
