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

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
3-540-46632-0_14.pdf154.19 kBAdobe PDF見る/開く
タイトル: Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle
著者: Iwama, Kazuo
Miyazaki, Shuichi
著者名の別形: 岩間, 一雄
宮崎, 修一
発行日: 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
出現コレクション:学術雑誌掲載論文等

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

Export to RefWorks


出力フォーマット 


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