[拼音]：feiquedingxing

[外文]：nondetermini

理论计算机科学中的一个重要概念。各种计算机器模型（自动机），在每一时刻，根据当时的状态和输入，若机器的动作可唯一确定时，则称机器为确定性的；若有多个动作可供选择时，则称机器为非确定性的。任意一种自动机，按其动作的确定程度，大体可分为确定的和非确定的两类。在对非确定性的研究中，一个核心课题就是非确定性能否增加机器的计算能力。具体说，对同一类自动机，确定型和非确定型机器在计算能力方面有没有区别？是什么关系？这类问题因其在理论上和实践中的重要意义而受到普遍重视。其中有些问题至今尚未解决，成为理论计算机科学中重要的悬案，NP=?P问题就是一个突出的例子。

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

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

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

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

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

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

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

严正声明：本文由历史百科网注册或游客用户逸春自行上传发布关于» 非确定性的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：逸春；本文链接：https://www.freedefine.cn/wenzhan/33069.html