复杂性类和算法复杂性之间的确切关系[重复

Question

这个问题在这里已经有一个答案：

• P，NP，NP-Complete和NP-HARD的定义是什么？ 7个答案

所有具有多项式时间复杂性的算法是否属于P类？ P类没有任何没有多项式复杂性的算法？

非多项式复杂性的所有算法均属于NP或NP-HARD还是两者兼有？

我只是想了解基本关系。

Answer 1

$ p $定义为具有（决策）问题的类别，该类别具有在多项式时间（在TM或多项式等值模型中）解决它们的算法。因此，$ p $完全包含这些问题，不再和更少。

至于$ np $ - 情况更加微妙。一个问题是$ np $，如果它具有在多项式时间内运行的非确定算法。一个等效，更易于用户友好的定义是给出了解决问题的解决方案，您可以在问题大小的时间内验证其正确性。例如，给定一个声称自己是哈密顿量的路径，您可以在多项式时间验证它确实是哈密顿路径。因此，确定图形是否具有哈密顿路径的问题是$ NP $。

澄清：$ np $是一类 问题, ，不是 算法. 。算法不属于$ NP $。

现在，已知有些问题没有多项式时间算法。这并不意味着它们在$ NP $中。实际上，已知某些问题不在$ NP $中。例如，任何$ nexp $ - hard问题。

关于$ np $ - hard问题 - 由于我们不知道$ p = np $，我们不知道$ p $以外的每个问题是$ np $ -hard。如果$ np = p $，则每个问题都是$ np $ -hard（$ sigma^*$和$ emptyset $除外）。

这个答案（到目前为止，这是不完整的）在基本的复杂性课程中涵盖了大约3周的材料。也许考虑彻底阅读教科书，例如Sipser的“计算理论”。

Answer 2

在多项式时间里解决了一些决策问题的所有算法都表明他们的问题在$ p $中。但是，肯定有一些算法在$ p $中不需要多项式时间。您可以通过生成所有输入的所有$ n！$排列来进行排序，并检查每个输入是否进行排序。该算法的确需要超过指数时间，但是问题在多项式时间内具有解决方案。