制限付集合に対する包除原理の性質と数え上げ問題への応用

スポンサーリンク

概要

論文の詳細を見る
n変数,m項DNF式F=∨^m_<i=1>T_iの充足割り当てを数え上げる問題について考える.項T_iを充足する入力の集合をA_iとし,S⊆{1,...,m}に対してa_S=|∩_<i〓S>A_i|とする.本稿では,Kahnらが示した"|S|≥logn+1である全てのSに対するa_Sの値のみによって,Fの充足割り当ての個数が一意に定まる"という定理の最適性を,すなわち,|S|≥lognであるSに対するa_SのみからではFの充足割り当ての個数が一意に定められないことを示す.さらに,各項に現れるリテラルの個数の最大値がtに制限された場合,|S|≥logt+2である全てのSに対するa_SによってFの充足割り当ての個数が一意に定まるが,|S|≥logt+1(t≥n/2)であるSに対するa_Sのみからでは一意に定められないことを示す.
2001-03-09

著者

関連論文

もっと見る

スポンサーリンク