並列化が徐々に困難になるグラフ問題について

スポンサーリンク

概要

論文の詳細を見る
計算複雑さがPからNP完全まで変化する「徐々に手に負えなくなる問題」は,多く知られてきた.たとえば,kクリーク問題のように最初に"k"のつく問題の多くにそのような性質がある.しかし,「並列化が徐々に困難になる問題」については,あまり知られていない.徐々に手に負えなくなる問題がPとNP完全の基本的な違いをうまく表すように,並列化が徐々に困難になる問題がNCとP完全に対して同様の役割を果たすことが期待される.本稿では,新たにα連結成分問題を提案し,その計算複雑さがαの値によってNCからP完全まで連続的に変化することを示す.より詳しくは,α連結成分問題は,(i)α=c(log n)^(t-2), 2>のときNC^tに入り,(ii)α=cn^εのときP完全になる.
1993-09-24

著者

関連論文

もっと見る

スポンサーリンク