非确定性

计算机学术语

所谓非确定性是指在理论计算机科学中，针对各种计算机器模型（自动机），在每一时刻，根据当时的状态和输入，若机器有多个动作可供选择时，则称机器为非确定性的；相反，若机器的动作可唯一确定时。且非确定性是相对于确定性来说，对于非确定性的机器，在性能各方面要高于确定性机器。

简介

任意一种自动机，按其动作的确定程度，大体可分为确定的和非确定的两类。在对非确定性的研究中，一个核心课题就是非确定性能否增加机器的计算能力。具体说，对同一类自动机，确定型和非确定型机器在计算能力方面有没有区别？是什么关系？这类问题因其在理论上和实践中的重要意义而受到普遍重视。其中有些问题至今尚未解决，成为理论计算机科学中重要的悬案,NP=?P问题就是一个突出的例子。

例子

一个单带图灵机，由一个有限控制器、一条输入带和相应的读写头组成。图灵机的动作是由有限控制器的状态和读写头扫视方格中的符号，依一定规则来定的。每一动作包括：改变机器的状态；在读写头扫视的方格中打印一个符号,以代替原来的符号;读写头向左或向右移一个方格。对于给定的状态和读写头读到的符号，图灵机的下一动作可能是唯一确定的，也可能有有穷多个动作可供选择。如果对于任何状态-符号对,下一动作都是唯一的，这种机器称为确定型单带图灵机；如果有有穷多个（包括零个或一个的情形）可以任意选择的下一动作，且规定对于给定的输入，只要在所有可能的动作序列中有一个序列导致接受状态,机器就接受其输入,这种机器就称为非确定型单带图灵机。对于确定型和非确定型的其他类型自动机，均可以类似地给出定义。

对于同一类型的自动机，确定型可以看作是非确定型的特殊情形。因此，非确定型的计算能力一般说应比确定型的强。然而是否真强，则取决于所讨论的自动机的类型。从自动机接受语言（见形式语言理论）的能力来说，对于有限自动机，确定型机器和非确定型机器接受的语言类完全一样，都是正规集合。对于下推自动机，确定型机器接受的语言类（确定的上下文无关语言）是非确定型机器接受的语言类（上下文无关语言）的真子类。例如，L={0i1j2k|i=j或j=κ}就是一个属于后者而不属于前者的语言。对于线性有界自动机，确定型机器和非确定型机器接受能力是否相等的问题，至今尚未解决,这就是著名的“LBA问题”。对于图灵机,已经证明确定机器与非确定机器具有相同的接受能力，它们所接受的语言类都是递归可枚举集合。

在计算复杂性理论中不仅考虑能不能计算的问题，还考虑计算时耗费资源（时间、空间等）的数量。在图灵机的情况下，如考虑资源界限，则对计算能力问题的回答便不一样。例如，当考虑多项式空间界限时，确定型图灵机接受的语言类PSPACE和非确定型图灵机接受的语言类 NPSPACE是相同的。而当考虑多项式时间界限时，就产生了著名的“NP=?P问题”。

问题研究

NP=?P问题

确定型图灵机在多项式时间内接受的语言所组成的类,记作P；非确定型图灵机在多项式时间内接受的语言所组成的类，记作NP。后者包含前者，但两者是否相同这个问题至今仍未解决。

关于NP=?P问题的研究,大体有四方面工作：借助归约方法进行的NP完全性理论的研究;借助ORACLE(橡树岭自动计算机和逻辑机)进行的相对化语言类的研究;结合各种语言时间（空间）复杂性类进行的研究；细分非确定性、可证明 NP和P等其他方面的研究。在研究过程中，有人试图证明NP=P;更多的则猜测并力图证明NP。有越来越多的人趋向于认为：NP=?P问题是独立于公理系统的，即在通常的公理化系统中，既不能证明NP=P，也不能否证它。

这个问题的研究，在理论和实践两个方面都具有重要意义。从理论上说，它使人们对非确定性这样一个重要概念的本质，有了越来越深的认识。同时,随着NP=?P问题研究的深入，引出了许多新的理论问题，它们都程度不同地和NP=?P问题相关。一旦NP=?P问题获得解决，就会导致一系列理论问题的解决。

其次，实践中的大量问题不是属于 P，就是属于NP。尽管图灵机能解决的问题都是可计算的,但普遍认为,只有属于 P的问题才是在计算机上现实可计算的。需要指数时间的问题虽然可计算，但因需要太多的时间，以致不被认为是现实可计算的。NP=?P问题就成为直接关系到NP中相当一批实际问题是否是“现实可计算的”这样一个大问题。实际上,若NP=P，那么NP中一切问题都是现实可计算的；但若NP≠P,NP中就将会有一批实际问题不是现实可计算的。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省