确定性计算与非确定性计算

---

要理解P类和NP类，首先我们应该了解计算模型。因此，在本章中我们将讨论两个重要的计算模型。

确定性计算和 P 类

确定性计算始终在初始状态期间提供与所有可用数据相同的输出。只要计算没有改变，就不存在随机性。

有多种模型可用于执行确定性计算 -

确定性图灵机

这些模型之一是确定性单带图灵机。该机器由有限状态控制、读写头和无限序列的双向磁带组成。

以下是确定性单带图灵机的示意图。

确定性图灵机的程序指定以下信息 -

• 有限的磁带符号集（输入符号和空白符号）
• 有限状态集
• 过渡函数

在算法分析中，如果一个问题可以通过确定性单带图灵机在多项式时间内解决，则该问题属于 P 类。

非确定性计算和 NP 类

非确定性图灵机

为了解决计算问题，另一种模型是非确定性图灵机（NDTM）。NDTM 的结构与 DTM 类似，但这里我们有一个额外的模块，称为猜测模块，它与一个只写磁头相关联。

以下是示意图。

如果问题可以通过非确定性图灵机在多项式时间内解决，则该问题属于 NP 类。