江西师范大学学报(自然科学版)
江西師範大學學報(自然科學版)
강서사범대학학보(자연과학판)
JOURNAL OF JIANGXI NORMAL UNIVERSITY
2003年
3期
279-282
,共4页
计算复杂性%NP完全性%方向关系推理
計算複雜性%NP完全性%方嚮關繫推理
계산복잡성%NP완전성%방향관계추리
空间方向关系推理问题的NP完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足问题,基于这种变换,空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关系限制;另一个变换是从不全等3可满足问题到方向关系限定满足问题,基于这种变换,3可满足问题实例中的变量可以变换为两个方向关系限制.为此,一个满足所有目标方向关系限制的空间结构可以建立,从而可以证明空间方向关系推理问题的NP完全性性质.
空間方嚮關繫推理問題的NP完全性證明是基于兩箇重要的變換基礎之上的,其中一箇變換是把空間方嚮關繫推理問題變換為一箇限定滿足問題,基于這種變換,空間方嚮關繫推理問題中的變量和值域相應地變換為限定滿足問題中的空間目標和方嚮關繫限製;另一箇變換是從不全等3可滿足問題到方嚮關繫限定滿足問題,基于這種變換,3可滿足問題實例中的變量可以變換為兩箇方嚮關繫限製.為此,一箇滿足所有目標方嚮關繫限製的空間結構可以建立,從而可以證明空間方嚮關繫推理問題的NP完全性性質.
공간방향관계추리문제적NP완전성증명시기우량개중요적변환기출지상적,기중일개변환시파공간방향관계추리문제변환위일개한정만족문제,기우저충변환,공간방향관계추리문제중적변량화치역상응지변환위한정만족문제중적공간목표화방향관계한제;령일개변환시종불전등3가만족문제도방향관계한정만족문제,기우저충변환,3가만족문제실례중적변량가이변환위량개방향관계한제.위차,일개만족소유목표방향관계한제적공간결구가이건립,종이가이증명공간방향관계추리문제적NP완전성성질.
