ダウンロード数: 204
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| 3-540-46632-0_14.pdf | 154.19 kB | Adobe PDF | 見る/開く |
| タイトル: | Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle |
| 著者: | Iwama, Kazuo Miyazaki, Shuichi   https://orcid.org/0000-0003-0369-1970 (unconfirmed) |
| 著者名の別形: | 岩間, 一雄 宮崎, 修一 |
| 発行日: | 1999 |
| 出版者: | Springer Berlin Heidelberg |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 1741 |
| 開始ページ: | 133 |
| 終了ページ: | 142 |
| 抄録: | Our main result shows that a shortest proof size of tree-like resolution for the pigeonhole principle is superpolynomially larger than that of DAG-like resolution. In the proof of a lower bound, we exploit a relationship between tree-like resolution and backtracking, which has long been recognized in this field but not been used before to give explicit results. |
| 記述: | 'Algorithms and Computation' 10th International Symposium, ISAAC’99 Chennai, India, December 16–18, 1999 Proceedings |
| 著作権等: | The final publication is available at Springer via https://doi.org/10.1007/978-3-642-45030-3_21 This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
| URI: | http://hdl.handle.net/2433/227017 |
| DOI(出版社版): | 10.1007/3-540-46632-0_14 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。