P问题/NP问题/NP-Hard问题/NP-Complete问题

近日,论文中涉及到NP-Hard问题,写下笔记对以上问题进行区分.

P问题:在多项式时间内可以求解的问题.

NP问题:在多项时间内不能求解,在多项式时间内可以验证的问题.

NP-Hard问题:所有的NP问题在多项式时间内可以归约到该问题,该问题为NP-Hard问题.

NP-Complete问题:一个问题即是NP-Hard问题,同时又是NP问题.