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

博文

“问题”的系统观(整体观)

已有 3933 次阅读 2015-4-21 10:08 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 问题, versus, 系统观

一,“问题”的中西文字源

1,英语(http://www.etymonline.com/index.php?term=problem

“problem”,源自希腊语:proballo = pro (in face of) + ballo (to throw),指橫在起点与目标之间的“障礙”。

另外,“人问问题”又是无法避免的事实,于是,又有另一词“question”来表达,“question”源自中世纪的“审判、调查”。

可见,“problem”和“question”于西文字源并无本质的联系。

2,汉字(汉字基因:http://www.hanculture.com/dic/v.php?id=850&m=jy

問題 = 問+題

問=門+口:門中有口,始能溝通,象徵求知。

題=是+頁:肯定重要者,標示 。

問題者,欲求知之主題。

从表意的角度,“问题”描述了一个场景:门外人敲门问问题,门内人开门回答问题。

二,“问题”的系统观

从字源看,中西文“问题”的最大区别是:于中文,提问者及回复者是显性的,突出了“主体”;而于西文,二者却是隐性的。也就是说,于汉字“问题”字源,“主体”容易进入视野,从而将之纳入考虑的对象,由此,可启发“问题”的系统观:“问题”既可指提问者和回复者的“介面”,也可指“提问者+未知事物+回复者”的“整体”,是有:

                    问题

提问者  ------->   回复者

            <-------

                   答案

释解:提问者向回复者提出问题;回复者为提问者提供答案。问题是关于未知事物的描述,而答案是关于未知事物的认知。

持此系统观,有利于对“问题”进行全面的考虑:

-若回复者给出的“答案”与“问题”一致,那么,可用“答案”直接指称“问题”;

-若因“问题”有难度,或因回复者不具备准确解答此问题的能力,回复者可能“答非所问”,在这种情况下,必须明确区分“答案”与“问题”、“提问者”和“回复者”的层次,故不能用“答案”直接指称或定义“问题”,而需将“答案”与“问题”的关系作整体考虑。

三,NDTM定义NP的认知错误

于“问题求解(problem solving)”,可得相应的“问题”系统观:

               问题

人  ------->   机器

     <-------

               算法

释解:于实际应用中,人提出问题,设计算法求解,机器执行算法,给出答案。

同样,持此整体观,可帮助认知“算法”与“问题”的关系,理清对“P versus NP”的混乱认知。

当求解的问题的难度在机器的计算能力范围内,如P类问题,存在着对应的“多项式时间算法”,“算法”与“问题”一致,故可用“多项式时间算法”或“图灵机(TM,DTM)”直接定义P类问题。

但是,当求解的问题的难度超出机器的计算能力,如NP类问题(不确定性问题),不存在多项式时间算法精确求解,仅存在多项式时间算法近似求解,在这种情况下,就不能用“算法”或“图灵机”定义NP,因为“算法”与“问题”不在同一层次,二者不一致。

NDTM定义NP,恰恰犯了这样的认知错误:用“确定性的算法”定义“不确定性问题”,因为NDTM的本质是DTM,所以,NDTM所定义的问题的本质只是P,而不是NP,换句话说,由NDTM定义的NP,其“不确定性”本质消失了,由此,导致了对NP认知的错误,“P versus NP”这件“皇帝的新衣”,遂成为世纪难题!

供大家进一步参详。




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

上一篇:不确定性图灵机(NDTM)与“不确定性”
下一篇:为什么还要讲“没用的NDTM”?(1)
收藏 IP: 82.246.87.*| 热度|

2 杨正瓴 zjzhaokeqin

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

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2024-12-24 09:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部