文献

J-GLOBAL ID：202202250483362098   整理番号：22A0902419

ランダム産業SATのモデル【JST・京大機械翻訳】

A model of random industrial SAT

著者 (3件)： Barak-Pelleg D. (Department of Mathematics, Ben-Gurion University, Beer Sheva 84105, Israel) ,  Berend D. (Departments of Mathematics and Computer Science, Ben-Gurion University, Beer Sheva 84105, Israel) ,  Saunders J.C. (Department of Mathematics, Ben-Gurion University, Beer Sheva 84105, Israel)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 910  ページ： 91-112  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： SATの最も研究されたモデルの1つはランダムSATである。このモデルでは,インスタンスは,それぞれ,ランダムに,そして,互いに独立的に選ばれた節から構成される。このモデルは,実世界アプリケーションにおいて生じるSATインスタンスの様々な特徴を記述するのに失敗するので不十分である。工業的SATのモデルを定義するために,様々な修正が示唆されてきた。ここでは,主にコミュニティ構造の側面に焦点を当てた。すなわち,ここでは,変数のセットは,多くの互いに素なコミュニティから成り,そして,節は,同じコミュニティからの変数から成る傾向がある。このように,ランダムSATに関する中心一般化が付加的コミュニティ構造であるランダム産業SATのモデルを提案した。ランダムk-SATの充足可能性閾値に関する多くの作業があり,2-SATの閾値の計算で始まり,閾値が十分に大きいkのために存在するという最近の結果まで始まった。本論文では,ランダム産業SATの提案モデルに対する充足可能性閾値を研究した。著者らの主な結果は,このモデルの閾値がランダムSATの対応物より小さい傾向があることである。さらに,いくつかの条件下で,この閾値は消えた。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 構造 ,  コミュニティ ,  応用プログラム ,  *モデル
準シソーラス用語： 互いに素 ,  コミュニティ構造 , 【Automatic Indexing@JST】

著者キーワード (5件)： SAT ,  産業用SAT ,  ランダムSAT ,  充足可能性閾値 ,  ボールとビン問題

分類 (5件)： マーケティング  (KA06020W) ,  農薬  (SB05030L) ,  機械的性質  (WB02030U) ,  流出過程およびそれに及ぼす影響  (DC07020C) ,  生物学的機能  (EB03040U)

タイトルに関連する用語 (3件)： 産業 ,  SAT ,  モデル