可逆回路内の縮退故障と短絡故障を検出するための最小検査入力集合を求める問題のNP困難性

摘要

可逆回路は非常に少ないエネルギー消費で計算が行えるためとても魅力的であり，様々な分野に応用が期待できる．よって，可逆回路製造時に回路内の故障を発見することはとても重要である．可逆回路内で短絡故障と縮退故障の両方を検出するための，最小検査入力集合を生成する問題の複雑さについての研究は，著者らの知る限りこれまで行われていない．本研究では，可逆回路に対し縮退および短絡故障を検出する最小の検査入力集合を生成することがNP-困難であることを示す．