NPC问题两个帖子
https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard
____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________| |
| P | Yes | Yes | |
| NP | Yes | Yes or No * | |
| NP-Complete | Yes | Unknown | |
| NP-Hard | Yes or No ** | Unknown *** | |
____________________________________________________________ V
P问题是可以在多项式复杂度内搜索并验证有效解。
NP问题是可以在多项式复杂度内验证
- P问题是NP问题的一种，搜索和验证都是多项式复杂时间。
- 搜索不是多项式时间， 验证是多项式时间。 这个是NP问题的重点
- 求出一个集合的所有子集。搜索是2^n, 验证是O（n）
- 关于P＝NP这个问题是未知的。目前看来NP分为NP complete和P两种， 找不出属于NP但是不属于NP complete和P的。如果找出来， 那么P!=NP 就做实了。相关研究还在继续
NPC问题是指NP问题中一些可以互相转换的问题, 这些问题能否在多项式时间内求解是未知的。
NP－hard问题更复杂，说是NP hard， 实际上和NP关系不大了。NP hard的问题即使解都不一定能在多项式时间复杂度内验证。如图灵机的halting problem
NP hard partition problem， 和google的optimal way转账一样。binary 搜索符合上下界的解法，然后多项式时间复杂度内验证。
居然是NP难
柯洁昨天0:3落后alpha Go，围棋属于exptime complete。
这个稍微难， 说有一堆task，每个有不同时间完成， 然后有一堆worker， 说如何分配 task to worker，完成时间最短， task是独立的。.看起来像背包， DP
task： 2，2，3，7， 1
worker： 2
解（2，2，3） （1， 7）注：task不一定是连续的，比如7，2，1，2，3 的解也是 （2，2，3） （1， 7）。应该是个多重背包
正确解法是二分搜索工作时间，然后验证。乍看是个多重背包NP问题， 实际是个P问题。binary Search上下限，验证解的正确性， 都是多项式复杂时间。 这个题和多背包问题相比，约束条件少很多，物品的体积都是1， 背包的空间（工人工作数量无限）。
LeetCode Optimal Account Balancing
http://www.cnblogs.com/grandyang/p/6108158.html
https://discuss.leetcode.com/topic/76158/11-liner-9ms-dfs-solution-detailed-explanation/4
这是个NP完全的题。