Home >

news ヘルプ

論文・著書情報


タイトル
和文:多くの充足解を持つ和積形論理式のインプリカントの大きさについて 
英文: 
著者
和文: ケイン ダニエル, 渡辺 治.  
英文: Daniel Kane, OSAMU WATANABE.  
言語 Japanese 
掲載誌/書名
和文:電子情報通信学会技術研究報告. COMP, コンピュテーション 
英文: 
巻, 号, ページ Vol. 114    No. 238   
出版年月 2014年9月10日 
出版者
和文:一般社団法人電子情報通信学会 
英文: 
会議名称
和文: 
英文: 
開催地
和文: 
英文: 
アブストラクト 任意の命題論理関数F(X_1,...,X_N)で,2^<-N>^δ・2^N個の充足可能解を持ち,さらに,高々N^d個の節から成るCNF論理式で表現できるものを考える(ただし,δ,0<δ<1とd<1は適当な定数).このとき,ある定数α>0が存在して,Fに対してある特定の高々αN個の変数の値を決めることで,その論理式を真にすることができることを示す.別の言い方をすれば,Fは,大きさ≦αNのインプリカントを持つことを示す.

©2007 Institute of Science Tokyo All rights reserved.