NP逻辑系统的归约关系研究

来源 :中山大学 | 被引量 : 0次 | 上传用户:yaoyao0313
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
逻辑系统在人工智能及计算机科学中有相当广泛的应用。人们不但利用它们来对知识进行表示和推理,还非常关心它们之间的表达能力关系。表达能力比较的标准并不唯一。一种经典的标准是逻辑等价关系,可是在这种比较标准下,许多具有非常不同特征的逻辑系统被认为是等价的。比如,命题逻辑、命题缺省逻辑、命题限制理论等在这个标准下是完全等价的,但前者是单调逻辑而后两者是著名的非单调逻辑且推理难度(指模型存在判定,下同)广泛认为比前者要高一层。这样,在逻辑等价关系下不能很好地区别各种逻辑系统。   另一种标准是由Gogic等提出的简洁性标准,即在逻辑等价的前提下,考察不同逻辑系统表示同一组模型时所需的公式长度,或者说知识库的大小。这种办法可以将逻辑等价的一些逻辑与另一些区别出来,比如命题缺省逻辑就比命题逻辑要严格简洁。但简洁性标准不考虑转换公式所需要的时间,也就是说,一个系统的知识库转换成等价的另一个系统下的知识库可能花指数时间。   赵希顺与Hans Kleine Buening提出了一种弱化的比较方法,即模型等价归约,这种转换不要求严格的逻辑等价性,但要求转换是可以快速计算的,而且转换前后的公式的模型有——对应的快速计算关系。这在实际应用中的意义是:模型等价归约允许我们快速地对一部分不同逻辑系统的知识库进行互相转换推理。比如回答集逻辑程序被认为是严格简洁于命题逻辑的,虽然它们的推理难度相同(均为NP完全),在要求刻画相同模型的情况下,一个逻辑程序转成命题逻辑公式最难时会有指数增长。但在模型等价归约下,它们表示能力是一样的,即我们可以快速地在两种数据库间进行转换推理。不过,模型等价归约并不能对同一推理难度完全实现互相快速转换,比如赵希顺与Hans KleineBuening等发现带存在量词的命题公式((E)PF)就似乎比命题逻辑,逻辑程序都要强,因此提出一个猜想:在模型等价归约下,(E)PF是模型判定问题在NP类中的那些逻辑系统中最强的吗?   本文对这个猜想作出以下回答:   ●在所有模型检测问题在NP中的NP逻辑系统中,(E)PF是最强的(极大的)。   ●在所有模型检测问题在P中的NP逻辑系统中,PF(命题逻辑)是最强的(极大的)。   ●一般而言,我们猜测不存在极大的NP逻辑系统,因为存在一些NP逻辑系统在多项式时间模型等价归约下是不可比较的。
其他文献
移动服务平台是一种具有复杂组织管理结构的大型服务平台,是运营商为终端用户提供服务的重要基础,其安全性关系重大,是各项增值业务有序运行的必要保证。   访问控制在信
在当今的时代环境下,Web程序的应用深入到人们生活中的方方面面,从资料搜索到新闻获取,从电子商务到网上办公,我们无时不刻的感受着网络时代的便捷。   为了满足人们对Web
国家电子政务基础信息库之一:自然资源与地理空间基础信息库(本文以下简称“信息库”)项目为满足电子政务对信息库基础信息的标准化需求,项目牵头单位拟编制自然资源与地理空间
随着微机电技术、计算技术和无线通信技术的发展,传感器在微小体积内已经能集成信息采集、数据处理和无线通信等多种功能,同时具有较低的能耗,此类传感器的出现推动了无线传感器
近年来,由于计算机技术迅速发展,越来越多的信息和资料开始摆脱传统的存储和展示媒介,向数字化的方式转变。其中,电信工程图纸作为指导电信工程施工,展示电信工程状况,保存电信工程
在当今这个信息化的社会,互联网在人们的生活和工作中起着越来越重要的作用。而利用网络进行的犯罪活动也日益增多,资料泄密和非法信息的传播就是其中的一种。电子邮件作为网络
随着Web2.0技术的发展,网络已经成为网民发表观点言论的重要渠道。如今,越来越多的网民在博客、论坛、评论互动和新闻组里发表他们关于社会时事和现象的态度和看法。而其中许
土地资源,是一种有限的资源,为人类提供粮食的土壤、安居的基础以及活动的依托。随着城市范围的扩大,越来越多的农用地、森林、荒地等被开发利用为城市中的建设用地,对土地开发利
21世纪科技日新月异,各种技术不断创新,大大改变了人们的生活方式。计算机的出现是一种变革性的社会进步,极大的推动了社会的发展。在此基础之上的各种应用技术的研究创新也
疲劳是人体的一种正常的生理活动,它是由于过度的脑力或体力劳动使人产生生理机能和心理机能的失调引起的,表现为瞌睡、精力不集中,同时人体的正常反应减慢。疲劳虽然是一种