Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(9)
发信站: 哈工大紫丁香 (2001年06月14日15:43:28 星期四), 站内信件

定义 NTM计算一个语言的特征函数的过程称为识别该语言.
记号 PTIME简写为P.NTM在多项式时间内可识别的语言集合记为NP.
定理 P是NP的子集.
注解 我们不知道P是否等于NP,真是计算机科学中最重要的问题之一.
定义 判定问题A在多项式时间内归结为问题B,是指对A的每个实例,
都存在B的一个实例,有一个多项式时间算法,能够从对B的实例的
解答算出A的实例的解答.简记为A=)B.
定义 一个判定问题B属于NPC iff 对NP中的任意判定问题A都有
A=)B.
定理 如果任何一个NPC与P的交集不空,那么P=NP.
定理 对P中的任意一个判定问题A,和NP中任意判定问题B,都有A=)B.
定理 对NP中的任意判定问题B,如果存在A属于NPC,使得A=)B,那么
B属于NPC.
注解 这是证明一个问题属于NPC的基本方法.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]