本稿では,2本の時間軸間の制約式に関する推論問題について述べる.まず,このような制約式の無矛盾性判定問題がNP完全であることを示す.次に,本稿では,制約式のグラフ表現の概念を導入する.もし,与えられた制約式cのグラフ表現が多項式時間で構成可能ならば,cの無矛盾性も多項式時間で判定できる.しかし,cがグラフ表現をもつかどうかの判定問題は一般にcoNP完全である.そこで,本稿では,グラフ表現が多項式時間で構成可能な制約式の部分クラスを提案する.このクラスは,これまで無矛盾性判定問題が多項式時間で解けることが知られているどのような制約式のクラスにも包含されない.