文献

J-GLOBAL ID：202002226363643283   整理番号：20A1800094

分解能からの単調回路下限【JST・京大機械翻訳】

Monotone circuit lower bounds from resolution

著者 (4件)： Garg Ankit (Microsoft Research, USA) ,  Goos Mika (Harvard University, USA) ,  Kamath Pritish (Massachusetts Institute of Technology, USA) ,  Sokolov Dmitry (KTH, Sweden)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2018  ページ： 902-911  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 分解能証明システムにおいて再分割が難しい任意の不満足CNF公式Fに対して,著者らは,Fのgadget-compedバージョンが,その線が効率的通信プロトコルによって計算され,等価的に,Fに関連する単調関数が,大きな単調回路複雑性を持つ,任意の証明システムにおいて,困難であることを示した。著者らの結果は,モノトーン実回路に拡張し,CuttingPlanes証明システムの新しい下限を与える。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *分解能
準シソーラス用語： 通信プロトコル ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (2件)： 回路の複雑さ ,  証明の複雑さ

分類 (3件)： 計算理論  (JB02000A) ,  論理代数  (JB03000H) ,  論理回路  (NC05070B)

タイトルに関連する用語 (2件)： 分解能 ,  下限