組合せ論理回路における故障検査問題の計算複雑度について
スポンサーリンク
概要
- 論文の詳細を見る
一般に組合せ回路の故障検査の問題はNP完全であり,NOT素子を含まない単調回路に対してもNP完全であることが知られている.本論文では,各外部入力に3以下の分岐を許し内部はANDとORだけから成る樹枝状構造をした論理回路を対象とし,そのように制限された回路に対する故障検査の問題でさえもNP完全であることを証明する.このことから,故障検査問題のNP完全性に影響するのは,一つの分岐点から再収れんする経路数ではなく,再収れんする分岐点の個数であることを明らかにするさらに,多項式時間で解ける一つのクラスとして分岐再収れん限定回路を紹介する.
- 一般社団法人情報処理学会の論文
- 1986-08-15