・ごくまれに遅いこともあるが, 一般的に見られる普通の問題に対しては高 速に解くことのできる``平均的に高速な解法''を考える場合.
・正確な解ではないかもしれないが, それに充分近いものを高速に見付けだ す``近似解法''を求める場合.
また, どのようなNP問題も多項式時間で あるNP完全問題に変換できることが知られ ているので, 個別のNP問題に対する解法を考えるのではなく, より一般的に1つのNP 完全問題を研究することによってNP問題を特徴づけし, あるいは高速な解法を考え るということもなされている.
本研究ではNP完全問題の1つの特徴づけでもあり, また人工知能などの分野でも重要 な充足可能性問題(SAT)をとりあげ, 以下の2点について考えていくことにした.
・平均的に高速といわれる解法に対しその高速性が実は平均をとるために使 用した入力モデルに依存することを確認するとともに, 入力のパラメータを変 化させることによって問題の難易度が劇的に変わることを確かめる.
・SATに対応する最適化問題である充足最大化問題(MAX SAT)に対する近似解 法を調べ, とくに最近発表された画期的な方法に関してはその本質を調べると ともに他の問題へ応用することを考える.