图问题（第一个不是NPC问题）
- 遍历所有边不重复 = 欧拉路径/一笔画问题
- 遍历所有点不重复 = 哈密顿回路问题
- 遍历所有边可以重复 = 中国邮递员问题（对无向图为P问题，对有向图为NPC问题）
- 遍历所有点可以重复 = 旅行商问题（TSP）
- 图着色问题：对一个无向图染色，满足相连点的颜色都不同，问最少需要多少种颜色
- 分团问题：问一个图中是否存在顶点个数为k以上的clique（一个子图，满足其中的顶点两两相连）
- 最小覆盖（虽然包括顶点覆盖和边覆盖，但实际只指顶点覆盖，只有顶点覆盖为NPC问题）：对图G，其中每个顶点均可覆盖所有以它为顶点的边，问最少选多少个点可覆盖所有的边
- 独立集：一个图中，黑色点相邻的必须是白色点，但白色点相邻的可以是黑色点也可以是白色点，问这个图中最多可以有多少个黑色点
- 子图同构问题（注意图的同构问题目前还未被证明为NP问题）
数学问题
- 背包问题（最优化描述）：对于给定容量的背包和给定价值以及大小的很多物品，问如何选择能使背包装的总价值最高
- 背包问题（确定性描述）：对于给定容量的背包和给定价值以及大小的很多物品，问能否选出物品总价值不超过V（在不超过背包容量的前提下）
- 子集和问题：给定一个整数集合，问是否存在子集，使其和为k
其它问题
- 扫雷
- 华容道问题/(n^2-1)数码问题
- 布尔可满足性质问题
参考链接