P问题:可在多项式时间内找到一个解的问题;(可解决)
NP问题:可在多项式时间内验证一个解的问题;(可验证)
NP-Complete问题:满足两个条件:1.是NP问题;2.任一NP问题都可转化为它;(可验证可规约)
NP-Hard问题:任一NP问题都可转化为它。(可规约)
关系图如下:
其中,整个圆表示NP问题,即NP问题包含P问题。
目前未解决的P=NP?难题可表述为:可在多项式时间内验证一个解的问题是否一定可在多项式时间内找到一个解?
参考:https://www.cnblogs.com/alantu2018/p/8464339.html