このアイテムのアクセス数: 2

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
IEICE_tec.rep_COMP99-33.pdf1.74 MBAdobe PDF見る/開く
タイトル: On the size of the tree-like resolution for the pigeonhole principle
その他のタイトル: 鳩の巣原理に対する木状導出原理の証明サイズについて
著者: Miyazaki, Shuichi
Iwama, Kazuo
著者名の別形: 宮崎, 修一
岩間, 一雄
キーワード: 導出原理
木状導出原理
鳩の巣原理
resolution
tree-like resolution
the pigeonhole principlethe
発行日: 3-Sep-1999
出版者: Institute of Electronics, Information and Communications Engineers (IEICE)
誌名: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
巻: 99
号: 288
開始ページ: 15
終了ページ: 22
論文番号: COMP99-33
抄録: We improve upper and lower bounds of the size of tree-1ike resolution refutation for the pigeonhole principle. These results imply the super-polynomial separation between the size of tree-like resolution refutation and that of DAG-1ike resolution refutation. Although a stronger result was already shown for this separation, our aim is to do the separation for the pigeonhole principle, which is one of the most famous CNF formula in this field. We use a novel technique for the proof of a lower bound; we exploit the equivalence between tree-1ike resolution and the backtracking, which is a well-known algorithm for the Satisfiability.
鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良を行なう.上下限の改良という本来の結果の他に, 木状導出原理による証明サイズが一般の導出原理に対するものよりも超多項式的に大きい例を, 最も研究のなされている鳩の巣原理に対しても示した.下限の証明には, 木状導出原理とSATアルゴリズムであるバックトラック法との等価性を利用した.
著作権等: © 1999 by the Institute of Electronics, Information and Communications Engineers (IEICE)
URI: http://hdl.handle.net/2433/227137
関連リンク: http://db.ieice.org/gakkai/show.php?id=114506
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。