An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem

Tong QIN; Osamu WATANABE

doi:10.1587/transinf.2021FCP0009

An Improvement of the Biased-PPSZ Algorithm for the 3SAT Problem

Tong QIN, Osamu WATANABE

Full Text Views

2

Cite this

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

3SAT, randomized algorithm, PPSZ, Biased-PPSZ, numerical analysis

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 -