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

博文

按标题搜索
Interpretation of NDTM in the definition of NP
热度 1 2016-12-17 15:24
我们的NP理论工作首重解读NP的二个流行定义及二个定义的关系,这篇英语文章是此工作的总结和深化。 文章追本溯源分析用于定义NP的NDTM(不确定性图灵机),揭示NDTM指称二个完全不同的概念:一个是Oracle(神喻机),另一个是Turing Machine(图灵机)。由于同一术语NDTM指称两个内涵完全不同的概念,故发生了“概念偷换 ...
个人分类: NP理论|3158 次阅读|3 个评论 热度 1
NP理论(4):判断如何成为算法
2016-9-21 17:22
人机关系最后落实到算法层次上可以说就表现在人的“判断”与机器的“判定”关系上,希尔伯特第十问题与图灵的回答一起作为“判定问题(Entscheidungsproblem)”,揭示了人的判断与机器的判定之间的不确定性关系,寻找这种不确定性关系的解决就可表达为“判断如何成为算法”。 一,丢番图问题[1] 丢番图问题:给定一个 ...
个人分类: NP理论|3682 次阅读|没有评论
NP理论(3):层次与中国传统逻辑
热度 3 2016-8-30 12:57
我们曾用中国传统逻辑的经典“白马非马”解析了流行的NP问题的两个定义中所隐含的层次上的混乱:基于“求解”,NP是NDTM(Non-Deterministic Turing Machine)多项式时间可求解的问题;基于“验证”,NP是DTM(Deterministic Turing Machine)多项式时间可验证解的问题。这二个定义被认为等价地表达了NP问题类。 我们认为 ...
个人分类: NP理论|4064 次阅读|3 个评论 热度 3
NP理论(2):“判定问题”与“停机问题”
热度 5 2016-7-18 23:20
计算机理论中现在流行的一个最基本术语就是“停机问题”(the Halting Problem),其基本意思是:判断任意一个程序是否会在有限的时间之内结束运行的问题。这种解释一开始就隐含了一个主体上的混乱,“判断者”是谁? 这个问题实质源于数学和逻辑基本理论,也就是著名的希尔伯特第十问题(Hilbert's tenth problem) ...
个人分类: NP理论|15820 次阅读|10 个评论 热度 5
NP理论(1):图灵机与丘奇-图灵论题
热度 4 2016-5-24 03:36
计算机理论的基础是可计算性理论,而可计算性理论的基石是“图灵机”与“丘奇-图灵论题”,其意义之丰富,涵盖了从数学、算法理论、数理逻辑以及哲学意义上的深刻内容,迄今仍然未被充分解读。 一,图灵机与丘奇-图灵论题的意义 我们把图灵机理解为“算法”,并强调“算法”具有“可计算性”的意义,丘奇-图灵论 ...
个人分类: NP理论|15013 次阅读|7 个评论 热度 4

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

GMT+8, 2024-3-29 20:56

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部