关于Karp猜想的一种新研究方法  

A new method of researching the Karp conjecture

作　　者：裴红梅[1] 黄桂丰[2] 

机构地区：[1]海军大连舰艇学院基础部,辽宁大连116018 [2]大连科技学院基础部,辽宁大连116052

出　　处：《辽宁师范大学学报（自然科学版）》2015年第1期13-16,共4页Journal of Liaoning Normal University:Natural Science Edition

基　　金：海军大连舰艇学院科研发展基金项目

摘　　要：关于图性质的Karp猜想是计算复杂性理论中的一个著名的悬而未决的问题,以往的研究方法仅仅是对某一种图性质进行研究,针对这一缺陷,给出了图性质的本质复杂性的概念,提出了以本质复杂性为基础的一种新的研究方法,这种方法的研究对象是一组满足某一特定条件的图性质,证明了只要其中一种图性质为诡的,这一组图性质均为诡的.Karp conjecture which deals with graph properties is still open and becomes a well-known difficult problem. The existing methods are focus on only one kind of graph property. To overcome the drawback of existing methods, this article defines the natural complexity of graph properties and proposes a new method. The new method is used to study a group of graph properties which are satisfy with some conditions. It has been proved that this new method could determine the elusiveness of a whole group of graph properties just by deciding one of the graph properies is elusive.

关 键 词：图性质 诡函数 Karp猜想 本质复杂性 

分 类 号：O157.6[理学—数学]