情報処理学会 第73回全国大会講演要旨

DNA計算とは、DNA分子の構造と分子生物学的な操作を活用して計算を行うことである。
本研究では、論理式の充足可能性問題(satisfiability problem；SAT)についてDNA計算を用いたアルゴリズムを提案した。DNA計算には、問題のサイズに対して解の候補のサイズが指数関数的に増大するというスケール問題を抱えており、これを克服するアルゴリズムとしてSuyamaらは幅優先探索法を用いて大幅に少ない分子量で3-SATをDNA計算で解いた。この幅優先探索法を利用して、k-SAT、SATを解くアルゴリズムを提案し、数値実験による分子量を比較を行った。