文献

J-GLOBAL ID：201802238731613207   整理番号：18A0853221

2CNF節のシステムにおける読み込み分解能再利用の発見【JST・京大機械翻訳】

Finding read-once resolution refutations in systems of 2CNF clauses

著者 (3件)： Buening Hans Kleine (Universitaet Paderborn, Paderborn, Germany) ,  Wojciechowski Piotr (LCSEE, West Virginia University, Morgantown, WV, United States of America) ,  Subramani K. (LCSEE, West Virginia University, Morgantown, WV, United States of America)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 729  ページ： 42-56  発行年： 2018年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文において,著者らは,1回分解能(ROR)避難方式の展望から2CNF式を分析した。著者らは,2つのタイプのROR給油に焦点を合わせた。すなわち,1回の避難と1回の避難である。前者において,各変数は避難の誘導においてほとんど一度使用されるが,後者においては,各クラスは一度使用される可能性がある。著者らは,与えられた2CNF公式がRORの避難を持つかどうかをチェックする問題が,両方の方式の下でNP完全であることを示した。これは驚くべきことに,2CNF式に対して,多項式時間避難スキーム(ツリー分解能とDAG分解能)が存在するという事実に照らしている。正側において,2CNF式はコピー複雑性2を有することを示した。このことは,任意の2CNF式が,ほとんど2回使用される必要があることを意味している。分解能避難方式の研究は,文献において多くの注意を受けた証明複雑性のサブフィールドである。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 避難 ,  *分解能 ,  再利用
準シソーラス用語： 複雑性 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (4件)： 2CNF ,  反論 ,  読み込み分解能 ,  可変読出し分解能

分類 (3件)： 計算理論  (JB02000A) ,  計算機網  (JC03000K) ,  符号理論  (ND02030R)

タイトルに関連する用語 (4件)： 読み込み ,  分解能 ,  再利用 ,  発見