整数線形不等式系の実行可能性問題における多項式時間可解部分クラス

摘要

本講演では，整数線形不等式系の実行可能性問題を扱い，その多項式時間可解部分クラスのまとめを行う．特に，整数線形不等式系の実行可能性問題の特殊な場合であるとみなせる充足可能性問題や単位整数線形不等式系における多項式時間可解部分クラスおよびそれらに対するアルゴリズムが，どのように一般の整数線形不等式系の実行可能性問題に拡張されるのかをみる．