论文部分内容阅读
关于图性质的Karp猜想是计算复杂性理论中的一个著名的悬而未决的问题,以往的研究方法仅仅是对某一种图性质进行研究,针对这一缺陷,给出了图性质的本质复杂性的概念,提出了以本质复杂性为基础的一种新的研究方法,这种方法的研究对象是一组满足某一特定条件的图性质,证明了只要其中一种图性质为诡的,这一组图性质均为诡的.