ダウンロード数: 74
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
IEICE_tec.rep_COMP99-33.pdf | 1.74 MB | Adobe 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) |
誌名: | 電子情報通信学会技術研究報告 |
巻: | 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 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。