不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

与法国朋友漫谈P vs NP(5)

已有 2023 次阅读 2020-5-20 20:09 |个人分类:不确定性问题和算法讨论|系统分类:科普集锦

柳渝:我用“ imaginaire (想象)一词指如您所说有些微妙NDTM,确实容易产生歧义。实际上,大致存在三种对NDTM的解释:

NDTM具有无限的并行能力;

NDTM可用TM在指数时间模拟;

- OracleCook原始关于NDTM的定义)。


我们暂时把基于有些微妙NDTM定义1”放在旁边,再考察一下基于TM定义2”


在人们的常识认知中,NPP是不同的。但是当人们希望对NP做深入的了解时,定义2”告诉人们:NP是图灵机多项式时间可验证解的问题类,由于P也是其解可以容易验证的问题类,所以NP包括P。注意,NPP的关系从相对关系变成了包含关系


所以,我问:这样的NP定义是否存在着问题?我现在试用一个比喻来说明我的质疑:

柳渝认识,但是没见过,一天她见到一群牛和一群在一起吃草,于是问您:

柳渝(指着马)问:这是什么?

Passe-Science:这是

柳渝:什么是

Passe-Science是有颜色的动物。


现在Passe-Science问柳渝:您知道什么是了吗?


柳渝只能回答:我不知道,因为牛也是有颜色的动物。



Passe-Science:我明白了混淆所在。根据定义,P包含在NP中是完全容许的。从结构上讲,无论哪种定义(定义1或定义2),P总是包含在NP中的。


如果问题是P,那么很明显,它可以在不确定性图灵机(定义1,因此也是NP)上多项式时间内求解,也可以在多项式时间内验证(定义2,因此也是NP)。


从来没有一个(P与NP)“对立”关系的定义,没有任何尝试能将NP定义为与P“不相交”的集,它们一直是包含关系,我们正在尝试的是研究这种包含关系是严格的,还是实际上相等的,NP中是否存在不在P中的元素。


关于“不相交”,应该是对“NP完全类”而言的,但显然我们不确定(因为是整个问题)NP中的“NP完全问题”在某种程度上是“最难”或“至少一样难”。如果我们有不同NP的P,那么P和NP-Complete之间是分离的。


参考文献:

对话原文见【1】https://www.youtube.com/watch?v=8TrIW-4kfRg







https://blog.sciencenet.cn/blog-2322490-1234129.html

上一篇:与法国朋友漫谈P vs NP(4)
下一篇:与法国朋友漫谈P vs NP(6)
收藏 IP: 85.171.213.*| 热度|

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-25 07:19

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部