ダウンロード数: 75
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
IEICE_tec.rep_COMP99-33.pdf | 1.74 MB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Miyazaki, Shuichi | en |
dc.contributor.author | Iwama, Kazuo | en |
dc.contributor.alternative | 宮崎, 修一 | ja |
dc.contributor.alternative | 岩間, 一雄 | ja |
dc.contributor.transcription | ミヤザキ, シュウイチ | - |
dc.contributor.transcription | イワマ, カズオ | - |
dc.date.accessioned | 2017-09-14T07:28:25Z | - |
dc.date.available | 2017-09-14T07:28:25Z | - |
dc.date.issued | 1999-09-03 | - |
dc.identifier.issn | 0913-5685 | - |
dc.identifier.uri | http://hdl.handle.net/2433/227137 | - |
dc.description.abstract | 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. | en |
dc.description.abstract | 鳩の巣原理に対する木状導出原理の証明サイズの上下限の改良を行なう.上下限の改良という本来の結果の他に, 木状導出原理による証明サイズが一般の導出原理に対するものよりも超多項式的に大きい例を, 最も研究のなされている鳩の巣原理に対しても示した.下限の証明には, 木状導出原理とSATアルゴリズムであるバックトラック法との等価性を利用した. | ja |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Institute of Electronics, Information and Communications Engineers (IEICE) | en |
dc.publisher.alternative | 電子情報通信学会 | ja |
dc.rights | © 1999 by the Institute of Electronics, Information and Communications Engineers (IEICE) | en |
dc.subject | 導出原理 | ja |
dc.subject | 木状導出原理 | ja |
dc.subject | 鳩の巣原理 | ja |
dc.subject | resolution | en |
dc.subject | tree-like resolution | en |
dc.subject | the pigeonhole principlethe | en |
dc.title | On the size of the tree-like resolution for the pigeonhole principle | en |
dc.title.alternative | 鳩の巣原理に対する木状導出原理の証明サイズについて | ja |
dc.type | research report | - |
dc.type.niitype | Research Paper | - |
dc.identifier.ncid | AN00349328 | - |
dc.identifier.jtitle | 電子情報通信学会技術研究報告 | ja |
dc.identifier.volume | 99 | - |
dc.identifier.issue | 288 | - |
dc.identifier.spage | 15 | - |
dc.identifier.epage | 22 | - |
dc.textversion | publisher | - |
dc.identifier.artnum | COMP99-33 | - |
dc.address | Graduate School of Informatics, Kyoto University | en |
dc.address | Graduate School of Informatics, Kyoto University | en |
dc.address.alternative | 京都大学情報学研究科 | ja |
dc.address.alternative | 京都大学情報学研究科 | ja |
dc.relation.url | http://db.ieice.org/gakkai/show.php?id=114506 | - |
dcterms.accessRights | open access | - |
dc.identifier.jtitle-alternative | IEICE technical report : 信学技報 | en |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。