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

博文

Interpretation of NDTM in the definition of NP

已有 2525 次阅读 2016-12-17 15:24 |个人分类:NP理论|系统分类:论文交流| oracle, definition, versus, 英语文章, interpret

我们的NP理论工作首重解读NP的二个流行定义及二个定义的关系,这篇英语文章是此工作的总结和深化。

文章追本溯源分析用于定义NP的NDTM(不确定性图灵机),揭示NDTM指称二个完全不同的概念:一个是Oracle(神喻机),另一个是Turing Machine(图灵机)。由于同一术语NDTM指称两个内涵完全不同的概念,故发生了“概念偷换”的逻辑错误,导致“可验证”成为现在NP的标准定义,自此NP的本质“不确定性”消失了,遂有“P versus NP”的千禧年难题。

由于NP的原始定义与Oracle有关,而Oracle又来自图灵关于“可计算性”的工作,故追本溯源到图灵的工作,应该是澄清NP定义的正途,也即我们的NP理论基于可计算性的深刻背景。

******

In this paper, we interpret NDTM (NonDeterministicTuringMachine) used to define NP by tracing to the source of NP. Originally NP was defined as the class of problems solvable in polynomial time by a NDTM in Cook’s theorem, where the NDTM was represented as Query Machine of essence Oracle. Later a model consisting of a guessing module and a checking module was proposed to replace the NDTM. This model of essence TM has a fundamental difference from the NDTM of essence Oracle, but people still use the term NDTM to designate this model, which leads to the disguised displacement of NDTM and produces out the verifier-based definition of NP as the class of problems verifiable in polynomialtime by a TM (Turing Machine). This verifier-based one has been then accepted as the standard definition of NP where comes from the famous equivalence ofthe two definitions of NP. Since then the notion of nondeterminism is lost from NP, which causes ambiguities in understanding NP and then great difficulties in solving the P versus NP problem.

Since NP is originally related with Oracle that comes from Turing’s work about Computability, it seems quite necessary to trace back to Turing’s work and clarify further the issue about NP.  

interpretationNDTMCiE.pdf



https://wap.sciencenet.cn/blog-2322490-1021326.html

上一篇:再谈为什么质疑NP的“可验证定义”
下一篇:“幸福的秘密”-亚眠杂技学校与长沙杂技学校圣诞联合演出

0

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

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

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

GMT+8, 2022-5-28 06:31

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部