np问题在不确定图灵机上是可以多项式时间得到解的

鉴于下面有人问为什么要这样定义时间，为什么用\log(n)而不是直接用n呢？ 原因是，对于某些问题，如果输入是n个元素，输入的长度往往不是n而是\log(n )，这是如果仍然使用n^k，它实际上代表的是指数时间，因为 ({ \log(n)})^{2k}=n^k。 当然，这也取决于您使用的型号。 例如，如果使用标准C模型，那么上述问题就不会存在。 然而，该模型并不适合所有问题。 例如，常见解决方案的运行时间为n^k，但实际上这是指数算法。

下面也有人提到“np问题可以在确定性图灵机上用多项式时间解决”。 这基本上是正确的，p意味着它可以在确定性图灵机上以多项式时间求解。 np 还有一个定义，即可以在确定性图灵机上以多项式时间验证问题的答案，但这已经是遥远的话题了，所以我不会谈论它。

凭记忆写的，如有错误请指出，谢谢