非決定性回路族における深さと非決定性ゲート数の関係

概要

論文の詳細を見る
言語を,計算の複雑さに基づいてクラス分けし,クラス間の包含関係を解明することは,理論計算機科学分野における最も基本的なテーマといえる.なかでも,P対NP問題の証明は,特に重要であり,解明に向けて様々な側面から研究が行われている.クラスNCは,ゲート数がnの多項式,深さ(段数)がlog nの多項式の対数一様論理回路族で受理される言語のクラスであり,NNC(g(n))は,NCにg(n)個の非決定性ゲートを導入したクラスである.NNC(g(n))は,g(n)を大きくすることで,クラスNPと等しくなることが知られており,NC,P,NP間のクラスの包含・等価関係を探求するのに適している.本稿では,非決定性回路族の深さと非決定性ゲート数の関係について調べる.ゲート数がnの多項式,深さがlog nの多項式の任意の非決定性回路族は,非決定性ゲート数を多項式の範囲で増やすことで,深さをO(log n)まで小さくできることを証明する.また,非決定性チューリング機械を,効率良く模倣する非決定性回路族の深さとゲート数についても述べる.
2011-04-15