文献

J-GLOBAL ID：201702279490401780   整理番号：17A1185841

充足可能性試験と制約プログラミングにおける一般解概念の確率論的研究【Powered by NICT】

A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming

著者 (2件)： Zhang Peng (Department of Computer Science, Irving K. Barber School of Arts and Sciences, University of British Columbia Okanagan, Kelowna, Canada V1V 1V7) ,  Gao Yong (Department of Computer Science, Irving K. Barber School of Arts and Sciences, University of British Columbia Okanagan, Kelowna, Canada V1V 1V7)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 657  号： PA  ページ： 98-110  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 割当の標準的概念を一般化したBoole充足可能性(SAT)と制約充足問題(CSP)のランダム事例の解の確率的挙動を研究した。著者らの解析は,一般解,(1,0)-超解の特殊型に焦点を当てた。k-SATのランダム事例では,k≦3のための導出確率の相転移の正確な閾値を定め,k≧4の場合の相転移のしきい値における上界および下界を与えた。CSP(制約充足問題)ために,確率1を持つ漸近的(1,0)-超解を持つのしきい値の上限を導出し,指数関数的に成長させる超解の期待数のための条件を確立した。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *確率論 ,  制約充足問題 ,  指数関数 ,  *制約プログラミング ,  相転移 ,  *一般解
準シソーラス用語： 下界 ,  上界 , 【Automatic Indexing@JST】

著者キーワード (7件)： 一般解概念 ,  超解 ,  充足可能性 ,  制約充足 ,  ランダムインスタンス ,  確率的方法 ,  しきい値現象

分類 (2件)： 人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 充足可能性 ,  試験 ,  制約プログラミング ,  一般解 ,  概念 ,  研究