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

博文

“NP问题是可计算的吗?” - 从“可计算性”的角度审视NP

已有 2013 次阅读 2020-12-31 16:53 |个人分类:不确定性问题和算法讨论|系统分类:论文交流


P vs NP世纪难题显示出在现有的计算机理论中存在着令人不安的困惑:一方面,书本中的NP问题理论部份无论是学习或教学都感到困难,以至于人们不得不一次又一次回头去重新学习或思考,但或者失望而返,或者强迫自己服从这些权威论述;另一方面,现有的NP问题理论与实际工作几乎完全脱节,甚至有人说完全可以不用此理论。进一步,包含现有的NP问题的计算机理论无法与正蓬勃发展的人工智能理论衔接。


2015年开设博客不确定性的困惑与NP理论以来,特别是2020年困难而特殊的一年,承蒙大家的热情支持和慷慨的帮助!这里,我们与大家分享关于P vs NP问题研究工作总结性的文章:“NP问题是可计算的吗?”- 可计算性的角度审视NP,希望对理清P vs NP问题的认知纠缠有所帮助,并祝大家新年愉快,来年顺利,。。。


题目: “NP问题是可计算的吗?

- 可计算性的角度审视NP


周剑铭 柳渝*(yu.li@u-picardie.fr

MIS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80090 Amiens, France


一,引言

二,NP定义溯源

三,现有的可计算性“NP问题是穷举法可计算的

1NP的形式定义

2,分析NP的形式定义

3,现有的可计算性所隐含的矛盾:图灵机可计算问题

四,图灵的可计算性“NP问题是穷举法可计算的吗?

1Entscheidungsproblem溯源

2,基于可计算序列判断问题

3可计算序列计算机器可计算问题

4“NP问题是穷举法可计算的吗?

五,案例研究:现有的图灵机” vs 图灵的计算机器

六,判定问题判断问题:判断的主体

七,结语


一,引言


在现有的计算机理论中,PPolynomial time)指图灵机在多项式时间可判定的问题类,但是对NPNondeterministic Polynomial time),情况却复杂得多,首先有一个教科书式的定义,“NP是不确定性图灵机在多项式时间可判定的问题类 NP is the class of problems decidable by Non-Deterministic Turing Machine (NDTM ) in polynomial time - 定义1),后来又发展出一个更通俗化的定义,“NP是图灵机在多项式时间可验证的问题类(NP is the class of problems verifiable by TM in polynomial time - 定义2)。于是,P vs NP问题被一般性表达为:NP=P?即多项式时间可验证的问题(NP)是多项式时间可判定的问题吗(P)? [1][2]


P vs NP问题成为计算机理论的重大的未解难题,还被Clay Mathematics Institute收录为七个千禧年难题之一。Gasarch2002年,2012年和2019年对P vs NP问题的前途进行了三次调查 [3],表明人们为寻找求解NP问题的多项式时间算法付出了巨大的努力,以求一举解决P vs NP难题,但是迄今为止并没有出现有价值的进展方向。


Hemaspaandra在介绍Gasarch的第二次调查时说 :我希望在遥远的未来,当人们读到这四篇文章(指介绍P vs NP问题的四篇文章),可以帮助他们了解,在“P vs NP”还没得到解决的黑暗年代里人们的思想状态(I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved) [4]


P vs NP问题的难点集中在对NP的认知上,表达为NP定义,关于NP的定义缠绕了计算机基本理论几十年,比如,Scott Aaronson在博客“The Scientific Case for P≠NP”说:似乎有一个看不见的电围栏P问题与NP完全的问题区分开 (there seems to be an "invisible electric fence separating the problems in P from the NP-complete ones) [5]


由流行的NP定义得出:“NP问题是穷举法可计算的,也就是说,NP定义的本质是对NP问题的可计算性的判断。然而,可计算性的判断是可计算性理论的核心议题,整个计算机理论由此展开,可是对于“NP问题的可计算性的判断,如此重要的议题,却几乎未见学术界展开讨论过。本文追本溯源回到图灵1936年那篇奠基可计算性理论的论文《论可计算数及其在判定问题上的应用》(On Computable Numbers, with an Application to the Entscheidungsproblem[6],对比现有的可计算性与图灵的可计算性,解读流行NP定义,探讨其对NP问题的可计算性判断的有效性,我们将看到对此质疑:“NP问题是穷举法可计算的吗?


二,NP定义溯源


NP作为概念“Non-deterministic Polynomial time”的提出源于柯克1971年那篇奠基性的论文,文中柯克提出后人称之的柯克定理,即论文中的定理1 [7]

定理1:如果一个符号串集合S被某种不确定性图灵机在多项式时间内接受,那末S可以被P-归约到{析取重言式}

Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.


由此,得出NP的第一个流行定义:

定义1 : NP is the class of problems decidable by NDTM in polynomial time


在柯克的论文中,NDTM原指由神谕机(Oracle Machine图灵机(Turing Machine混合而成的查询机(Query Machine,查询机的计算行为被解释为:对于一个NP问题实例,神谕机可解,此可由图灵机多项式时间验证。然而,由于神谕机不是构造性的机器模型,在现实中并不存在,为了将神谕机从NDTM中排除,学界遂将NDTM的计算行为解释为猜测+验证” [8]  ,即对于一个NP问题实例,NDTM在多项式时间猜测出一个候选解,并能在多项式时间验证。经过这样的解释,NDTM就从查询机变成了现在的多选择的NDTM”,即相对于在计算的下一步只有唯一的选择TMNDTM可以有多选择” [9]。于是,得到NP的第二个流行定义:

定义2 : NP is the class of problems verifiable by TM in polynomial time


定义1与定义2被认为等价 [10]NDTM又被解释为与TM等价,“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”Sipser书,Theorem 3.16), 于是有了一个非形式的承认TM在指数时间内模拟NDTM的计算。 

由此人们很快就认可,NDTM的计算行为与穷举法等同,这样NP又被解释为“NP是穷举法可计算的问题类,毕竟PNP不同,于是就有了“NP问题是可计算的,但难计算的这样的流行观念。

不管以后的解释如何,在直觉认知上,NPP是不同的,但是NP的定义又给人NPP等价的指望,这就是P vs NP问题的困难之源。

三,流行的可计算性“NP问题是穷举法可计算的


首先,我们讨论NP的形式定义。

1NP的形式定义


这里我们考虑Papadimitriou的书计算复杂性的第9章给出的NP的形式定义 [11]Cook在为Clay Mathematics Institute介绍P vs NP问题时也给出了类似的定义 [1]

- 令R为二进制字符串的关系; 即,让R为一组有序对(x,y)的集合,其中xy是二进制字符串。 如果存在确定性图灵机在多项式时间内判定给定的(x,y)是否在R中,我们则说R多项式可判定。如果 k >= 1 使得对于R中的所有(x,y)y的长度(我们写为| y |)最大为|x|^k,则R多项式平衡(Let R be a relation on binary strings; i.e., let R be a set of ordered pairs (x,y) where x and y are binary strings.  We say that R is "polynomially decidable" if there is a deterministic Turing machine that decides in polynomial time where a given (x,y) is in R.  We also say that R is "polynomially balanced" if there is some k >= 1 such that for all (x,y) in R, the length of y (which we write as |y|) is at most |x|^k.)

- 现在我们准备定义NP 语言LNP中,当且仅当存在多项式可判定且多项式平衡的关系R,使得语言L = {x : (x,y)R中存在y}时。(Now we are ready to define NP.  A language L is in NP if and only if there is a polynomially decidable and polynomially balanced relation R such that L = {x : (x,y) is in R for some y}.)


2,分析NP的形式定义


NP的形式定义涉及集合LR,让我们以SAT,典型的NP问题为例,从解读LR开始。


2.1 集合LR


考虑2SAT实例:


f1 = (x1 x2 x3)(x1 x2 x3)(x1 x2   x3) (x1 x2 x3)f13个变元,共2^3=8个变元赋值组合,其中4个是f1的解,R = {(f1,(0 1 0)), (f1,(0 1 1)), (f1,(1 0 1)), (f1,(1 1 1))}


f2= x1 ¬x1, 1个变元,共有2个变元赋值的组合,f2无解,R = Ø


对于Lf1可满足,在L中;f2不可满足,不在L中,故L = { …, f1, …}


所以,RSAT的给定实例的所有解的集合,而LSAT的所有可满足的实例的集合:

- R = {(x,y) : x是SAT的实例,y是x的解}

- L = {x : 存在某个y,使得(x,y) 在R中} 


下面我们按照这个方法定义SAT,很快能看到,P面向判定问题,而NP面向判断问题


2.2 “判定问题判断问题


记集合A = {x G(x)表示x满足某种性质},表达元素x与集合A的所属关系,即整体中个体,而判断x是否在A中,即判断元素x是否具有性质G(x)


从这个理解出发,SAT呈现出二个层次上的定义:

判定问题:穷举法判定SAT问题的给定实例x是否可满足。这相当于,穷举法判定x的给定候选解y是否在R中。

判断问题:如果穷举法可以判定SAT实例(R),那么穷举法是否可以判定SAT问题(L)?


可见,判定问题面向“实例”(个体,R),而判断问题面向“问题”(整体,L),所以NP的形式定义是基于对判断问题的回答。实际上,我们也能看到,这个回答才是造成现有的NP定义的困难的根源。


对于判定问题,通过枚举SAT实例x的所有候选解y,重复调用多项式时间验证解的图灵机M,就可以在指数时间判定x是否可满足,所以穷举法对判定SAT实例x具有可计算性。


但要注意,这个意义上的穷举法并没有产生一个新的图灵机与之对应,就是说,不过是重复调用多项式时间验证解的图灵机M,因此这里的指数时间只是表达重复调用M,是一个由暗中定义了的指数时间复杂度。所以,判定问题的本质是“P问题


根据NP的形式定义,语言LNP中,当且仅当存在多项式可判定且多项式平衡的关系R,使得语言L = {x : (x,y)R中存在y}”,就是说,穷举法判定SAT实例与穷举法判定SAT问题等价,换句话说,在判定问题判断问题之间建立起了越界的等价关系!


这也正是NP的非形式定义1与定义2“等价所表达的意义:“NP is the class of problems verifiable by TM in polynomial time”“NP is the class of problems decidable by NDTM in polynomial time”等价。


所以,流行NP定义是对NP问题的可计算性的直接肯定,而非论证,实例与问题的关系从“整体中的个体”变成个体即整体判断问题因此被取消了,从而失去了揭示NP本质的可能性,暗含NP=P。下面我们从现有的可计算性观念中追究更一般性的原因。


3,流行的可计算性所的隐含的矛盾:图灵机可计算问题


在现有的计算机理论中,可计算问题被解读为,可计算问题是由停机的图灵机计算的问题,图灵机的无限长的纸带被解读为无限的时空,所以图灵机的计算被解释为不计时空开销。这样的可计算问题理论上似乎是可计算的,但物理上却不一定是可计算的。


图灵机模型使用无限长纸带作为其无限内存,有一个读写头。最初,输入字符串被放置纸带上,纸带的其他方格均为空白。机器将继续计算,直到决定产生输出为止。 通过进入指定的接受和拒绝状态来判断是否接受和拒绝输入,如果图灵机不进入接受或拒绝状态,则将永远持续下去,永不停止。[10](Sipser书,Theorem 3.16

- The Turing machine model uses an infinite tape as its unlimited memory. It has a tape head that can read and write symbols and move around on the tape. Initially the tape contains only the input string and is blanc everywhere else. If the machine needs to store information, it may write this information on the tape. To read the information that it has written, the machine can move its head back over it. The machine continues computing until it decides to produce an output. The outputs accept and rejet are obtained by entering designated accepting and rejecting states. If it doesn’t enter an accepting or a rejecting state, it will go on forever, never halting. 


既然图灵机的计算不计时空开销,那么穷举法计算NP问题的实例与计算NP问题(任意实例)就没有区别,这就是判定问题判断问题之间越界的等价关系的来源!


现在让我们追本溯源回到图灵的可计算性理论,考察“NP问题是穷举法可计算的有效性。


四,图灵的可计算性“NP问题是穷举法可计算的吗?


作为计算机理论的核心概念,可计算性表达了“算法”普遍性的解决问题的过程性能力,对这种过程性能力的考察被数学家隐含地表达出来,这就是著名的希尔伯特(David Hilbert 18621943)的Entscheidungsproblem:是否存在通用过程来判定任何可定义的数学问题可解。


Entscheidungsproblem 这一词由于历史时间不同,具有不同的具体表达形式。


1Entscheidungsproblem溯源


Entscheidungsproblem源于希尔伯特1900年所作的《数学问题》的著名讲演,其中提出了数学理论中的23个最困难的问题,第10问题是这样说的[13]: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. 


作为一个大数学家希尔伯特并没有用数学方法函数形式方法这样现成的术语,而是问:能否设计一个过程To devise a process)来判定determine)任何一个丢番图方程问题是否可解?


1936年的文章中,图灵证明:不存在通用过程判定任何一阶谓词公式可证。


2,基于可计算序列判断问题


为此,图灵理解性说[6] :对这样一个通用过程的问题可以表达为通用过程判定给定的整数n是否具有性质G(n)的问题(比如,G(n)可能表示“n是可满足的’’“n是一个可证明公式的Godel表达),这相当于计算一个数,如果G(n)为真,其第n个数字为1;如果G(n)为假,其第n个数字为0For each of these "general process" problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G{n) might mean "n is satisfactory" or "n is the Godel representation of a provable formula"], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.


与上述基于语言NP的形式定义相比,图灵引入了可计算数(序列)computable numbers/sequence)概念,表示机器写下的所有实例的计算结果,而将给定实例的计算结果置于此序列中,表达了实例与问题的整体中个体的关系,也就是说,“判定问题”包含在“判断问题”中。


可计算数(序列)成为图灵工作的红线,贯穿于整个论文中,正如 Charles Petzold在其书The Annotated Turing所说 [12]:

- “尽管解决Entscheidungsproblem确实是图灵写这篇文章的动机,但是这篇长篇大论本身讲的却是可计算数。在图灵的定义中,可计算数就是可以使用机器计算的数。论文前面60%的内容都是对可计算数的探索。


让我们考察图灵是如何从可计算数(序列)出发定义可计算性的。


3可计算序列计算机器可计算问题


图灵在论文开篇提出可计算数computable numbers),强调是由机器写下来的 [6] :

- 按照我的定义,一个数是可计算的,如果它的十进制的表达能被机器写下来。(According to my definition, a number is computable if its decimal can be written down by a machine.


接着,图灵将人计算实数与机器计算过程进行比较,构造出作为现代计算机模型的计算机器computing machine),写下可计算数(序列)computable number/séquence)

- 如果一台机器打印两类符号,第一类(称为数字)全是01,其它被称为第二类符号,则机器将被称为计算机器。如果给机器装置一条空白纸带,让它运动起来,从正确的初始m-格局出发,机器打印的第一类符号的子序列称作机器计算的序列;在表达为二进制的十进制实数前放上小数点,称作机器计算的数。(If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.


图灵进一步区分Circular machineCircle-free machine

- 如果计算机器只写下第一类有限数目的符号,被称作“Circular”;否则,被称作“circle-free”。(If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free.


然后,再用Circle-free machine的计算过程明确定义可计算数(序列)Computable sequences/numbers

- 一个序列被说成可计算的,如果能够通过一台“circle-free machine”计算而得。一个数是可计算的,如果它与由“circle-free machine”计算的数只差一个整数。(A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle- free machine.


并且说:

- 为了避免混淆,我们更经常说可计算序列,而不是可计算数。(We shall avoid confusion by speaking more often of computable sequences than of computable numbers.


这样,可计算序列算法(计算机器)问题之间建立起可能存在的某种实质性的联系,可计算问题是计算机器写下可计算序列的问题。由此,图灵的可计算性表达了通用性整体性实时性


对比上述流行的“可计算问题,图灵定义的可计算问题不仅在理论上是可计算的,而且在物理上也是可计算的


4“NP问题是穷举法可计算的吗?


从图灵的可计算性的角度,SAT表达为判断问题”: 

- 判断问题:是否存在计算机器判定SAT的给定实例fn可满足,这相当于计算序列αL = G(f1)G(f2)G(f3)... G(fn)…(G(fn)表示fn是可满足的实例),如果G(fn)=1,fn是可满足的;否则,fn是不可满足的?


所以考察“穷举法”对SAT问题是否具有可计算性,就是考察“穷举法”能否写下SAT问题的可计算序列αL = G(f1)G(f2)G(f3)…G(fn)…


如以上分析,穷举法判定SAT的给定实例,是通过重复调用多项式时间验证解的计算机器M而具有指数时间复杂度,所以穷举法的本质就是计算机器M,而穷举法的指数增长的计算开销能否胜任SAT的实例规模的增长,即能否计算αL = G(f1)G(f2)G(f3)…G(fn)…成为了问题,换句话说,多项式时间验证解的计算机器MSAT问题是否具有可计算性成为了问题,是有问题:“SAT是穷举法可计算的吗?


实际上,对“SAT是穷举法可计算的吗?的判断进入了计算复杂性理论的论域,而对SAT可计算性的一般性判断则与图灵论文的主题希尔伯特的Entscheidungsproblem密切相关,需要专门讨论,不是本文的主题。


五,案例研究:现有的图灵机” vs 图灵的计算机器


为了进一步理解现有的可计算性与图灵的可计算性的区别,我们以判定任意自然数的奇偶性为例,对比图灵机与图灵的计算机器


1图灵机” 


判定问题:判定所有的自然数n的奇偶性,这相当于判定任意的自然数n是否在偶数集合A中,A = {n : mod(n, 2)=0}


比如n=2mod(2, 2)=0,故2A中;n=3mod(3, 2)/=0,故3不在A中。


这里,假设输入的自然数用真数表示:11),211),3111),。。,;输出1表示偶数;输出0表示奇数。


图灵机M1的规则表:

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, qY

q2, #, 0, R, qN


q1表示初始状态qYt表示接受状态”, qN表示拒绝状态qYqN都是停机状态


模拟M在输入(n=2)的运行:

开始的纸带放置11 Rule ):

 1   1   #   #   # …

内态的变化:

q1 q2  q1 qY.

纸带的变化:

#   #   1   #  # …


模拟M在输入(n=3)的运行:

开始的纸带放置任给的一个自然数:

 1   1   1   #   # …

内态的变化:

q1 q2  q1 q2 qN.

纸带的变化:

#   #   #   0  # …


2,图灵的计算机器


根据图灵对判断问题的表达:


判断问题:判定所有的自然数n的奇偶性(G(n)表示n是偶数,n mod 2 = 0),这相当于计算序列010101…,如果G(n)为真(偶数),序列的第n个数字为1;如果G(n)为假 (奇数),序列的第n个数字为0


其可计算序列记为,α = G(1)G(2)G(3)…G(n),。。。= 010101…

G(1)=0    (n=1, 奇数)

G(2)=1  n=2, 偶数)

G(3)=0    (n=3, 奇数)

。。。


图灵在论文中给出的第一个计算机器的例子就是计算序列010101…,但图灵是将此序列作为十进制数0.333…的二进制数表示,所以没有考虑输入数据,纸带的输入只是空白符号“#”blank),其对应的计算机器的规则表如下:

q1, # , 0, R, q2

q2, # , # , R, q3

q3, # , 1, R, q4

q4,# , # , R, q1


模拟此机器的运行:

#   #   #   #   #   #  …

q1 q2 q3 q4 q1 q2 …

0   #   1   #   0   #  …


我们将序列010101…作为对所有自然数(1,2,3,…)奇偶性的判断结果,纸带上的输入数据是用真数表示的所有自然数:11),211),3111),。。,;输出1表示偶数;输出0表示奇数。


所以需要上述计算机器M1的规则表略作修改成M2

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, q1

q2, #, 0, R, q1


此机器的初始状态是q1,没有停机状态。在q1状态下遇空白符“#”,写下“1”,表示输入的自然数是偶数,然后回到初始状态q1q2状态下遇空白符“#”,写下“0”,表示输入的自然数是奇数,然后回到初始状态q1,继续判断纸带上的下一个自然数。


模拟此图灵机的运行:

开始的纸带:

1   #   1   1   #   1   1   1   # …

内态的变化:

q1 q2 q1 q2 q1 q1 q2 q1 q2 q1, …

纸带的变化:

#   0   #   #   1   #   #   #   0 …


可见,现有的图灵机M1)与图灵的计算机器M2)之间存在着微妙的差别:计算机器计算完一个实例然后回到初始状态,不停机继续计算下一个实例,无限长的纸带对应无限长的可计算序列circle-free machine),表达计算机器的计算能力的“通用性”。所以,计算机器虽然没有对计算一个实例的时空开销进行规定,但是并非指计算一个实例不计时空开销


而现有的图灵机”加入了停机状态,计算完一个实例就停机(接受与拒绝),遂将无限长的纸带解读为计算一个实例不计时空开销


六,集合与判断:判断的主体


如上述分析,NP定义的本质是对NP问题的“可计算性”的判断,但是流行的NP定义将判定问题等价于判断问题,直接得出“NP问题是可计算的判断。我们从集合与判断的角度,进一步分析其原因。


康托最初给出的集合定义 [14]:

- 集合是我们感知或思想到的不同的对象的聚集而成的整体,这些对象称为集合的元素。

- A set is a gathering together into a whole of definite, distincts objects of our perception [Anschauung] or of our thought  - which are called elements of the set.


就是说,集合表达的是对元素与集合的所属关系,即整体中个体判断


判断涉及到判断的主体,在一般情况下主体,人运用感知或思想进行判断。当人借助于数学和逻辑进行判断,论域是数学;但是人当借助于算法来进行判断时,判断的主体成了机器,论域就从数学转移到了算法。虽然数学和算法都使用符号,但其组织性质完全不同,数学是纯粹的形式关系,与物理无关;而算法则一定是实时Actual Time)过程,与时空有关。


在流行的NP定义中,判定问题穷举法判定NP问题的给定实例x是否可满足,判断的主体是图灵机(算法),算法与时空有关,然而在现有的可计算性理论中,图灵机的无限长的纸带被解释为不计时空图灵机因此失去了算法的物理性质,实际上成为了神喻机,也就是说,判断的主体从图灵机偷换成了神喻机!所以,穷举法判定NP问题的实例与判定NP问题就没有了区别,直接得出“NP问题是可计算的判断,从而取消了“人作为判断的主体的“判断问题”,流行NP定义暗含NP=P


可见,在现有的可计算性理论中,存在着判断主体的混淆,导致对个体与整体关系认知的混淆,暗中用个体即整体替代了整体中个体,这正是流行NP定义所隐藏的认知错误的来源,所谓数学家的误解” [15]


七,结语


我们追本溯源回到图灵1936年那篇奠基可计算性理论的论文《论可计算数及其在判定问题上的应用》,解读流行的NP定义,质疑“NP问题是穷举法可计算的流行观点。


通过对比分析,我们指出现有的可计算性与图灵的可计算性之间有出入。首先,体现在对NP问题的二种表达中:

- 基于语言NP问题;

- 基于可计算序列NP问题。


然后是图灵机与图灵定义的计算机器之间存在着微妙的差别:

- “图灵机完成对一个实例的计算而停机无限长的纸带被解释为计算一个实例不计时空开销

- 图灵的计算机器完成对一个实例的计算后回到初始状态,然后不停机继续计算下一个实例。


由此导致关于可计算问题的二种观点:

- 现有的可计算问题是图灵机不计时空开销计算但能停机的问题,在物理上不必是可计算的。

- 图灵的可计算问题是计算机器能写下可计算序列的问题,在理论物理上的可计算性是一致的。


我们从集合与判断的角度,分析在现有的可计算性理论中存在着判断主体的混淆,导致判定问题判断问题的混淆。我们认为欲解决P vs NP问题,需要正视对NP问题的可计算性判断问题,这就意味着需要追本溯源审视对图灵机可计算性计算复杂性,停机问题等计算机理论的基本议题的认识。本文所介绍的工作就是这方面的初步尝试。


我们的工作提示,图灵的著作和工作虽然已经近百年了,尽管在技术实践上取得了巨大的成就,但在图灵的主要理论基础上并没有取得跨越性的进步,甚至已经被作为计算机理论圣经的图灵机仍然蒙着一层神秘的面纱,比如问

- 为什么现在的图灵机与图灵的计算机器之间存在着微妙差别?

- 为什么可计算序列(数)的概念从现有的计算理论中消失了?


图灵处在世界格局重构的年代,数学和科学理论的大厦己经耸立,工业技术与纯粹理论正在融汇而走向一个全新的信息时代,图灵有幸成为了这个转折点,我们並不期望直接从图灵的论著中找到现成的答案,而是希望通过他的著作去理解他深刻而隐秘的思想,从中获取灵感,用我们的智慧去参与和回应时代面临的挑战,比如P vs NP问题的挑战,。。。


参考文献:


[1] Stephen Cook,  P vs NP Problem (http://www.claymath.org/millennium-problems/p-vs-np-problem)

[2] A Most Profound Math Problem (http://www.newyorker.com/tech/elements/a-most-profound-math-problem) May 2 2013, the New Yorker.

[3] Guest Column: The Third P =? NP Poll William I. Gasarch (https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf)

[4] William I. Gasarch, The P=?NP poll. SIGACT News Complexity Theory Column 74. http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf

[5] S. Aaronson.  The Scientific Case for P≠NP (https://www.scottaaronson.com/blog/?p=1720)

[6] Turing, A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (published 1937), 42 (1), pp. 230–65 (https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf)

[7] Stephen Cook, The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151-158 (1971). (http://theory.stanford.edu/~trevisan/cs172-07/cook.pdf)

[8]  Garey Michael R., David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and company (1979) 

[9] Michael Sipser. Introduction to the Theory of Computation, Second Edition. International Edition (2006) 

[10]  JianMing Zhou, Yu Li, Inquiry of P-reduction in Cook’s 1971 Paper -from Oracle machine to Turing machine. 

http://arxiv.org/abs/1905.06311 

[11] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley Edition (1994). 

[12]  Charles Petzold, The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine. John Wiley & Sons, Inc. (2008). 

[13] Hilbert's tenth problem (https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem)

[14] https://en.wikipedia.org/wiki/Set_(mathematics)

[15] David Deutsch, Constructor Theory David Deutsch. https://arxiv.org/pdf/1210.7439.pdf

 









http://blog.sciencenet.cn/blog-2322490-1265098.html

上一篇:简介电影《春江水暖》
下一篇:“世界逻辑日” (2021/1/14)

3 刘钢 杨正瓴 崔树勋

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

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

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

GMT+8, 2021-12-1 00:46

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部