| Item type |
SIG Technical Reports(1) |
| 公開日 |
2021-04-30 |
| タイトル |
|
|
タイトル |
3SAT 問題に対するBiased-PPSZ アルゴリズムの改良 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
株式会社牧野フライス製作所SIT本部 |
| 著者所属 |
|
|
|
東京工業大学情報理工学院 |
| 著者所属(英) |
|
|
|
en |
|
|
SIT Division, Makino Milling Machine Co., Ltd. |
| 著者所属(英) |
|
|
|
en |
|
|
School of Computing, Tokyo Institute of Technology |
| 著者名 |
秦, 同
渡辺, 治
|
| 著者名(英) |
Tong, Qin
Osamu, Watanabe
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Hansen，Kaplan，Zamir and Zwick (STOC 2019) は，3SAT 問題を解く PPSZ アルゴリズムの計算過程で確率分布の「偏り」を用いる手法を提案し，彼らが具体的に定義した偏りに基づく PPSZ アルゴリズムの改良版を用いると，Unique 3SAT 問題に対して，PPSZ よりかなりの計算効率の改善が得られることを示した．この報告では，さらに別の偏りの利用法を提案し，その方法によりさらなる改善が得られることを数値解析的に示す． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Hansen, Kaplan, Zamir and Zwick (STOC 2019) introduced a systematic way to use “bias” for predicting an assignment to a Boolean variable in the process of PPSZ and showed that their biased PPSZ algorithm achieves a relatively large success probability improvement of PPSZ for Unique 3SAT. We propose an additional way to use “bias” and show by numerical analysis that the improvement gets increased further. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2021-AL-183,
号 6,
p. 1-8,
発行日 2021-04-30
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL21183006.pdf (899.0 kB)
