組合せ問題のアルゴリズムの効率化に関する研究

点击翻译按钮获取中文摘要

主に以下の四点の成果を上げた。1.代表的な組合せ問題である、和積形論理式(CNF式)充足解数数え上げ問題に関してk-CNF式の解総数を一意に定めるためには、各項を非充足とする変数割当ての集合の変数の数に関する多項式個の情報を持つことが必要十分であることを示した。また、同結果を応用し、ハイパーグラフの彩色数を一意に定めるための必要十分条件を示した。2.1に関してk-CNF式の充足解数を実際に求めるアルゴリズムを陽的に構築した。3.CNF式に対して、充足解の総数を充足解に含まれる1となる変数の数に関する事前知識を仮定することで、各々準指数時間、多項式時間の効率的なアルゴリズムが存在することを示した。4.計算理論に関し、従来任意の整数nとαが与えられたときに、2^n-α個の状態を持つ決定性有限オートマトンと等価なn状態非決定性有限オートマトンが存在するかどうかは知られていなかったが、本研究により、n【greater than or equal】7、5【less than or equal】α、【less than or equal】2n-2である全てのn、αに対しては、そのような非決定性有限オートマトンが存在することが示された。