p与np

这是一个算法上的一个经典的概念，在看状态压缩dp的时候看到了，之前学算法的时候并没有太深入研究所以这边仔细看了看然后记录了一下概念。

p问题

即能用DTM(deterministic Turing Machine)在多项式时间内解决的问题

NP问题

即能用NDTM（non-deterministic Turing Machine)在多项式时间内解决的问题。NDTM的概念即图灵机之间每个状态的转移是不确定的，没有学过编译原理的无法理解这个事情，不过你可以理解成有一个精灵，在图灵机每次进行选择的时候总是告诉他正确的路。还有另外一个容易判断的定义，即一个NP问题的解可以被一个DTM在多项式时间内验证。