“
制約充足問題に関してはかなり成功しました． 制約充足問題とは，変数の集合と制約の集合が入力として与えられ，変数に値を代入して変数の間の制約を全て/出来るだけ多く満たすというものです． 例えば，グラフのk彩色性，kSAT，有限体上の線形連立方程式などが制約充足問題で表現できます． ここでは検査したいことは，与えられた入力の全ての制約を充足出来るかどうかです． この問題に対して定数時間で検査可能な制約充足問題の必要十分条件を得ることが出来ました． 必要十分条件の雰囲気としては「局所的に入力を見るだけで充足性の判定が出来るような制約充足問題なら検査も簡単，そうでなければ難しい」です．
