IEICE TRANSACTIONS on Information
An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.481-490
- Publication Date
- 2022/03/01
- Publicized
- 2021/09/08
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021FCP0009
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
- Category
Authors
Tong QIN
SIT Division, Makino Milling Machine Co., Ltd.
Osamu WATANABE
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tong QIN, Osamu WATANABE, "An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 481-490, March 2022, doi: 10.1587/transinf.2021FCP0009.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0009/_p
Copy
@ARTICLE{e105-d_3_481,
author={Tong QIN, Osamu WATANABE, },
journal={IEICE TRANSACTIONS on Information},
title={An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem},
year={2022},
volume={E105-D},
number={3},
pages={481-490},
abstract={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.},
keywords={},
doi={10.1587/transinf.2021FCP0009},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem
T2 - IEICE TRANSACTIONS on Information
SP - 481
EP - 490
AU - Tong QIN
AU - Osamu WATANABE
PY - 2022
DO - 10.1587/transinf.2021FCP0009
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - 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.
ER -
English
