文献

J-GLOBAL ID：201702227802019774   整理番号：17A1385483

ランダム3CNFのための空間証明複雑性【Powered by NICT】

Space proof complexity for random 3-CNFs

著者 (6件)： Bennett Patrick (Mathematics Department, Western Michigan University, United States) ,  Bonacina Ilario (School of Computer Science and Communication KTH Royal Institute of Technology, Sweden) ,  Galesi Nicola (Computer Science Department, Sapienza University of Rome, via Salaria 113, 00198 Rome, Italy) ,  Huynh Tony (Department of Mathematics, Universite Libre de Bruxelles, Boulevard du Triomphe, B-1050 Brussels, Belgium) ,  Molloy Mike (Computer Science Department, University of Toronto, 10 Kings College Road, M5S 3G4 Toronto, Canada) ,  Wollan Paul (Computer Science Department, Sapienza University of Rome, via Salaria 113, 00198 Rome, Italy)
資料名： Information and Computation  (Information and Computation)
巻： 255  号： P1  ページ： 165-176  発行年： 2017年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 分解能と代数系における3CNFを反論の空間計算量を調べた。n変数におけるランダム3-CNFφの分解能反論を有した全ての多項式計算は記憶で同時に維持するΩ(n)の明確な単項式を高い確率で必要とすることを証明した。また,同じ構成法により,φの各分解能反論は,高い確率で,Ω(n)は記憶で同時に維持される幅Ω(n)のそれぞれを指標が必要であることを証明した。これはφを否定する分割における必要な全空間のための下界Ω(n 2)与えた。これらの結果は最良可能である(一定倍まで)と3CNFの空間複雑性についての質問に答えた。主技術革新はH allの補題の変種である。分割(L , R)と左度最大で3の二部グラフにおける,Lは互いに素な経路のある族,ε<15のVW-マッチングと呼ばれる,Lは(2 ε)の因子によるRが拡大すること,によりカバーできることを示した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 代数系 ,  マッチング ,  計算量 ,  多項式 ,  *分解能
準シソーラス用語： 互いに素 ,  二部グラフ ,  *複雑性 ,  下界 , 【Automatic Indexing@JST】

著者キーワード (6件)： 証明複雑性 ,  多項式計算 ,  単項空間 ,  ランダムCNF ,  分解能 ,  全空間

分類 (3件)： 論理代数  (JB03000H) ,  人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (1件)： 証明複雑性