P，NP，NPC，NP-hard问题

     （文中所指的“难、易”是指计算复杂度的相对大小）:

    P问题

     P问题(Polynomial Problem，多项式问题)，P问题指是可以在多项式时间里被确定性图灵机（通常我们使用的计算机）解决的问题。

    NP问题

     NP问题(Non-Deterministic Polynomial Problem, 非确定多项式问题),是指可以在多项式时间里被非确定性图灵机解决的问题。或者另一种定义，NP问题是指确定性图灵机可以在多项式的时间里验证一个problem的解但不确定能否在多项式内解决该problem的问题。

     注：验证和解决是不同的，如：解决自然语言处理问题和验证自然语言处理问题是否被解决是不同的，验证的困难性明显更低。

            非确定性图灵机：现实并不存在的计算机，能够每次都猜到问题的解，和量子计算机不同，但计算能力比量子计算机更强。

             P与NP问题是否等价，等价于能否找到一个或多个算法，使确定性图灵机在多项式时间里解决所有的NP问题。

    NPC问题

     NPC问题（Non-deterministic Polynomial Complete Problem，NP完全问题），简单来说，NPC问题是指能在多项式时间里转化（规约）为一般NP问题的NP问题，且NPC问题比所有一般的NP问题更难。

    NP-hard问题

     NP-hard问题（Non-deterministic Polynomial Hard Problem，NP难问题），NP-hard问题与NPC问题的唯一区别是NP-hard问题不一定是NP问题，即NP-hard问题是指能在多项式时间里转化（规约）为NP问题的问题。