-
题名关于Karp猜想的一种新研究方法
- 1
-
-
作者
裴红梅
黄桂丰
-
机构
海军大连舰艇学院基础部
大连科技学院基础部
-
出处
《辽宁师范大学学报（自然科学版）》
CAS
2015年第1期13-16,共4页
-
基金
海军大连舰艇学院科研发展基金项目
-
文摘
关于图性质的Karp猜想是计算复杂性理论中的一个著名的悬而未决的问题,以往的研究方法仅仅是对某一种图性质进行研究,针对这一缺陷,给出了图性质的本质复杂性的概念,提出了以本质复杂性为基础的一种新的研究方法,这种方法的研究对象是一组满足某一特定条件的图性质,证明了只要其中一种图性质为诡的,这一组图性质均为诡的.
-
关键词
图性质
诡函数
Karp猜想
本质复杂性
-
Keywords
graph property
elusive function
Karp conjecture
natural complexity
-
分类号
O157.6
[理学—基础数学]
-
-
题名图性质的Karp猜想
被引量：1
- 2
-
-
作者
李德英
堵丁柱
-
机构
华中师范大学数学系
中国科学院数学与系统科学研究院
-
出处
《科学通报》
EI
CAS
CSCD
北大核心
2000年第20期2129-2133,共5页
-
文摘
所有非平凡、单调的图性质的判定树复杂性等于, 其中n是图的顶点数. 这就是关于图性质的Karp猜想. 综述关于Karp猜想的研究进展.
-
关键词
Karp猜想
判定树
诡函数
图论
逻辑问题
-
分类号
O157.5
[理学—基础数学]
-
