命題論理式を充足可能性が等価な連言標準形に変換する方法であるTseytin変換（Tseytin Transformation）について紹介します．

有限オートマトンによって認識不可能な言語を非正規言語と呼ぶ．ここでは，ある言語が非正規言語となることを示すのによく用いられるポンピング補題について紹介する．

問題. 755 整数 が与えられる． 以上 以下の整数のうち，各桁が数字 '3', '5', '7' のいずれかで，かつ，'3', '5', '7' の数字が少なくとも1回以上現れるものの数を求めよ．制約：

問題. Shortest Common Non-Subsequence '0' と '1' からなる2つの文字列 が与えられる． と のどちらの部分文字列でもない '0' と '1' からなる文字列で最小の長さのものを求めよ．ただし，答えが複数ある場合は辞書順で最小のものを求めよ．制約：

問題. What Goes Up Must Come Down 非負整数列 が与えられる． の隣り合う2要素を交換するという操作を繰り返して を山型にしたい．ただし，数列 が山型であるとは，ある要素 が存在して， となることである．数列 を山型にするための交換回数の最小値を求…

問題. Arithmetic Progressions 非負整数からなる集合 が与えられる． の部分集合で等差数列となるものの中で要素数最大のものを見つけ，その要素数を答えよ．制約： ，