コモンスーパシーケンスに関する判定問題の計算複雑さ

菊野 亨  吉田 典可  若林 真一  

誌名
電子情報通信学会論文誌 D   Vol.J64-D   No.4   pp.356-363
発行日: 1981/04/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(653KB)>>
論文を購入




あらまし: 
プログラムテキストの編集,分子生物学におけるアミノ酸系列の分子相互間の関係を求める問題などに対する基礎的研究として,任意に与えられた系列の集合Rに対し,その最大共通部分系列および最小共通超系列を求める問題は興味ある問題であり,今までに多くの報告がなされている.Maier(1978年)は,nn2)個の系列を含む系列の集合Rの最大共通部分系列,最小共通超系列を求める問題に関連し,それぞれLCS問題,SCS問題と呼ばれる判定問題を新たに定義し,それらがNP-完全となることを示した.本論文ではSCS問題に注目し,以下に示すSCS問題の三つの部分問題の計算複雑さについて議論し,これらがいずれもNP-完全であることを示す.(1)Rに属する各系列の長さを制限した場合(問題S1),(ii)Rに属する各系列においてアルファベットΣの各要素がたかだか1回しか現れない場合(問題S2),(iii)アルファベットΣの大きさ(|Σ|)を3とした場合(問題S3).本論文の結果は,いずれもMaierのNP-完全性の結果を更に強めたものとなっている.