NP问题

可以在多项式的时间里验证一个解的正确性，或者，可以在多项式的时间里猜出一个解的问题

P问题

如果一个问题可以找到一个能够在多项式的时间里解决它的算法，就属于 P 问题

指向原始笔记的链接

NPC问题

首先是一个 NP 问题，所有的 NP 问题都可以约化到 NPC 问题

指向原始笔记的链接

NP-hard问题

满足 NPC问题 的第一条不满足第二条

指向原始笔记的链接